Створення БІнарного Дерева Пошуку

Бінарним Деревом Пошуку (БДП) називається бінарне дерево з коренем, що має наступні властивості:

• Ліве піддерево містить лише вершини, значення яких строго менші за корінь.

• Праве піддерево містить лише вершини, значення яких строго більші за корінь.

• Усі значення вершин різні.

• Ліве та праве піддерево рекурсивно є бінарним деревом пошуку.

При вставці нової вершини запускається наступний алгоритм:

1. Якщо дерево порожнє, то нова вершина стає коренем і процес вставки завершується. Інакше перейти до кроку 2.

2. Оголосимо поточною вершиною корінь дерева.

3. Якщо значення нової вершини менше кореня, то:

   • Якщо ліве піддерево кореня порожнє, то встановимо нову вершину лівим сином кореня і зупиняємся.

   • Інакше встановимо поточною вершиною корінь лівого піддерева і повторимо крок 3.

4. Якщо значення нової вершини більше кореня, то:

   • Якщо праве піддерево кореня порожнє, то встановимо нову вершину правим сином кореня і зупиняємся.

   • Інакше встановимо поточною вершиною корінь правого піддерева і повторимо крок 3.

Структура БДП залежить від вхідної послідовності. Різні послідовності можуть породжувати різні структури, не дивлячись на те, що числа у них однакові.

Розглянеемо послідовність 1 2 3. Отримаємо наступне БДП:

Якщо вхідна послідовність має вигляд 2 1 3, то отримаємо дерево

З іншого боку, різні вхідні дані можуть породжувати однакові БДП структури. Наприклад, вхідна послідовність 2 1 3 породжує таку ж саму структуру БДП, що і послідовність 4 6 2. Дерево матиме вигляд:

За заданими n вершинами БДП визначити, скільки різних вхідних послідовностей утворюють ту ж саму БДП структуру, що й задана. Вершини дерева приймають значення з діапазону 1..m.

Вхідні дані

Перший рядок містить кількість тестів t (t ≤ 100). Кожний тест починається з двох цілих чисел n та m (1 ≤ n ≤ m ≤ 1000) - кількість вершин у БДП та максимальне значення діапазону відповідно. Наступний рядок містить n цілих чисел a_i (1 ≤ a_{i }≤ 1000) - послідовність, з якої будується БДП.

Вихідні дані

Для кожного тесту потрібно вивести кількість різних послідовностей, які утворюють одну й ту ж БДП структуру, вважаючи, що значення беруться з діапазону 1..m. Результат потрібно виводити по модулю 1000003.

Примітка: Пояснення до другого тесту.

Є 8 вхідних послідовностей (дані взято з проміжку 1..4), які формують одну і ту ж структуру БДП:

1. 2 1 3

2. 2 3 1

3. 2 1 4

4. 2 4 1

5. 3 1 4

6. 3 4 1

7. 3 2 4

8. 3 4 2

Приклади