Создание Бинарного Дерева Поиска

Бинарным деревом поиска (БДП) является дерево с корнем, обладающее следующими свойствами:

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

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

• Все значения вершин разные.

• Левое и правое поддерево рекурсивно является бинарным деревом поиска.

При вставке новой вершины запускается следующий алгоритм:

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

Примеры