Бінарним Деревом Пошуку (\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}