Counting BST

A binary search tree (BST) is a rooted binary tree with the following properties:

• The left subtree of a node contains only values smaller than the node's value.
• The right subtree of a node contains only values greater than the node's value.
• All values in the tree are distinct.
• Both subtrees are themselves binary search trees.

A BST is built by inserting values one at a time. To insert a new value:

1. If the tree is empty, the new value becomes the root.
2. Otherwise, start at the root and make it the current node.
3. If the new value is smaller than the current node's value, move to the left child; if that child is empty, place the new value there.
4. If the new value is greater than the current node's value, move to the right child; if that child is empty, place the new value there.
5. Repeat until the new value has been placed.

The shape of the resulting tree depends on the order in which the values are inserted. The same set of values inserted in a different order can produce a different shape, and different sets of values can produce the same shape. For example, inserting $1, 2, 3$ in that order yields a right-leaning chain, while inserting $2, 1, 3$ yields a balanced tree; the sequences $2\ 1\ 3$ and $4\ 6\ 2$ produce the same shape.

You are given a BST defined by one insertion sequence of $N$ values. Count how many distinct insertion sequences of $N$ distinct values chosen from the range $1 \dots M$ produce a tree with exactly the same shape. Because this count can be large, report it modulo $1{,}000{,}003$.

The first line contains an integer $T$ ($T \le 100$), the number of test cases.

Each test case consists of two lines. The first line contains two integers $N$ and $M$ ($1 \le N \le M \le 1000$): the number of nodes in the tree and the size of the value range. The second line contains $N$ distinct integers $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 1000$), the insertion sequence that defines the tree's shape.

For each test case, output on its own line the number of distinct insertion sequences using values from $1 \dots M$ that produce the same tree shape, taken modulo $1{,}000{,}003$.