Binary Search Tree (BST) is a rooted binary tree data structure which has following properties: \begin{itemize} \item Left subtree contains only nodes with value less than the node's value. \item Right subtree contains only nodes with value greater than the node's value. \item All values in the nodes are unique. \item Both left and right subtrees are also binary search tree recursively. \end{itemize} If there is a new node to be inserted, the following algorithm will be used: \begin{enumerate} \item If the root is empty, then the new node becomes the root and quit, else continue to step 2. \item Set the root as current node. \item If the new node's value is less than current node's value: \begin{itemize} \item If current node's left is empty, then set the new node as current node's left-child and quit. \item else set current node's left-child as current node, and repeat step \textbf{3}. \end{itemize} \item If the new node's value is greater than current node's value: \begin{itemize} \item If current node's right is empty, then set the new node as current node's right-child and quit. \item else set current node's right-child as current node, and repeat step \textbf{3}. \end{itemize} \end{enumerate} BST structure depends on its data inserting sequence. Different sequence may yield a different structure though the data set is the same. For example: Insert sequence: \textbf{1} \textbf{2} \textbf{3}, the BST will be: \includegraphics{https://static.e-olymp.com/content/aa/aacfb5495e16cf9a9ff0de6ddfaadb5c0e480c5c.jpg} If the data is inserted with sequence: \textbf{2} \textbf{1} \textbf{3}, the tree will be: \includegraphics{https://static.e-olymp.com/content/bd/bde2d8a71d1925e70c02c11d4c8a899f3b44786c.jpg} On the other hand, different data set may have a same BST structure. For example: Insert sequence \textbf{2} \textbf{1} \textbf{3} will have the same BST structure with \textbf{4} \textbf{6} \textbf{2}, and the tree will be: \includegraphics{https://static.e-olymp.com/content/81/81416f010093212239d97b6e8dfc9d6027f0d20e.jpg} Given \textbf{n} nodes BST, calculate how many distinct insert data sequence which result in the same BST structure, assuming that data are taken from range \textbf{1}..\textbf{m}. \InputFile The first line contains the number of test cases \textbf{t} (\textbf{t} ≤ \textbf{100}). Each case begins with two integers \textbf{n} and \textbf{m} (\textbf{1}\textit{ }≤ \textbf{n} ≤ \textbf{m} ≤ \textbf{1000}), the number of nodes in BST and the maximum range respectively. The next line contains \textbf{n} integers \textbf{a_i} (\textbf{1} ≤ \textbf{a}_\{i \}≤ \textbf{1000}) the insert sequence that construct a BST. \OutputFile For each case, output an integer denoting the number of distinct insert data sequence which result in the same BST structure, assuming that data are taken from range \textbf{1}..\textbf{m}. Modulo this number with \textbf{1,000,003}. \textit{\textbf{Note}}: Explanation for the \textbf{1}^st sample input. There are \textbf{8} insert sequences (data taken from \textbf{1}..\textbf{4}) which have the same BST: \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}