Бинарным деревом поиска (\textbf{БДП}) является дерево с корнем, обладающее следующими свойствами: \begin{itemize} \item Левое поддерево содержит только вершины, значения которых строго меньшие корня. \item Правое поддерево содержит только вершины, значения которых строго больше корня. \item Все значения вершин разные. \item Левое и правое поддерево рекурсивно является бинарным деревом поиска. \end{itemize} При вставке новой вершины запускается следующий алгоритм: \begin{enumerate} \item Если дерево пустое, то новая вершина становится корнем и процесс вставки заканчивается. Иначе перейти на шаг \textbf{2}. \item Объявим текущей вершиной корень дерева. \item Если значение новой вершины меньше корня, то: \begin{itemize} \item Если левое поддерево корня пусто, то установим новую вершину левым сыном корня и останавливаемся. \item Иначе установим текущей вершиной корень левого поддерева и повторим шаг \textbf{3}. \end{itemize} \item Если значение новой вершины больше корня, то: \begin{itemize} \item Если правое поддерево корня пусто, то установим новую вершину правым сыном корня и останавливаемся. \item Иначе установим текущей вершиной корень правого поддерева и повторим шаг \textbf{3}. \end{itemize} \end{enumerate} Структура БДП зависит от входной последовательности. Разные последовательности могут порождать разные структуры, несмотря на то, что числа в них одинаковые. Рассмотрим последовательность \textbf{1} \textbf{2} \textbf{3}. Получим следующее БДП: \includegraphics{https://static.e-olymp.com/content/aa/aacfb5495e16cf9a9ff0de6ddfaadb5c0e480c5c.jpg} Если входная последовательность имеет вид \textbf{2} \textbf{1} \textbf{3}, то получим дерево \includegraphics{https://static.e-olymp.com/content/bd/bde2d8a71d1925e70c02c11d4c8a899f3b44786c.jpg} С другой стороны, разные входные данные могут порождать одинаковые БДП структуры. Например, входная последовательность \textbf{2} \textbf{1} \textbf{3} породит ту же структуру БДП, что и последовательность \textbf{4} \textbf{6} \textbf{2}. Дерево будет иметь вид: \includegraphics{https://static.e-olymp.com/content/81/81416f010093212239d97b6e8dfc9d6027f0d20e.jpg} По заданным \textbf{n} вершинам БДП определить, сколько различных входных последовательностей образуют ту же самую БДП структуру, что и заданная. Вершины дерева принимают значения из диапазона \textbf{1}..\textbf{m}. \InputFile Первая строка содержит количество тестов \textbf{t} (\textbf{t} ≤ \textbf{100}). Каждый тест начинается с двух целых чисел \textbf{n} и \textbf{m} (\textbf{1}\textit{ }≤ \textbf{n} ≤ \textbf{m} ≤ \textbf{1000}) - количество вершин в БДП и максимальное значение диапазона соответственно. Следующая строка содержит \textbf{n} целых чисел \textbf{a_i} (\textbf{1} ≤ \textbf{a}_\{i \}≤ \textbf{1000}) - последовательность, из которой строится БДП. \OutputFile Для каждого теста вывести количество разных последовательностей, образующих ту же самую БДП структуру, что и входная последовательность. Вершины дерева принимают значения из диапазона \textbf{1}..\textbf{m}. Результат следует выводить по модулю \textbf{1000003}. \textit{\textbf{Примечание}}: Объяснение второго теста. Имеется \textbf{8} входных последовательностей (данные взяты из промежутка \textbf{1}..\textbf{4}), которые формируют одну и ту же структуру БДП: \begin{enumerate} \item \textbf{2 1 3} \item \textbf{2 3 1} \item \textbf{2 1 4} \item \textbf{2 4 1} \item \textbf{3 1 4} \item \textbf{3 4 1} \item \textbf{3 2 4} \item \textbf{3 4 2} \end{enumerate}