이진 탐색 트리 개수 세기

이진 탐색 트리(BST) 는 다음 성질을 만족하는 루트 있는 이진 트리이다.

• 한 노드의 왼쪽 서브트리에는 그 노드보다 작은 값만 들어 있다.
• 한 노드의 오른쪽 서브트리에는 그 노드보다 큰 값만 들어 있다.
• 트리에 있는 모든 값은 서로 다르다.
• 두 서브트리 또한 각각 이진 탐색 트리이다.

BST는 값을 하나씩 삽입하여 만든다. 새 값을 삽입하는 방법은 다음과 같다.

1. 트리가 비어 있으면 새 값이 루트가 된다.
2. 그렇지 않으면 루트를 현재 노드로 삼는다.
3. 새 값이 현재 노드의 값보다 작으면 왼쪽 자식으로 내려간다. 그 자식이 비어 있으면 그 자리에 새 값을 놓는다.
4. 새 값이 현재 노드의 값보다 크면 오른쪽 자식으로 내려간다. 그 자식이 비어 있으면 그 자리에 새 값을 놓는다.
5. 새 값이 놓일 때까지 이 과정을 반복한다.

만들어지는 트리의 모양 은 값을 삽입하는 순서에 따라 달라진다. 같은 값들의 집합이라도 삽입 순서가 다르면 다른 모양이 될 수 있고, 서로 다른 값들의 집합이 같은 모양을 만들 수도 있다. 예를 들어 $1, 2, 3$ 순서로 삽입하면 오른쪽으로 치우친 사슬 모양이 되고, $2, 1, 3$ 순서로 삽입하면 균형 잡힌 트리가 된다. 또한 $2\ 1\ 3$ 과 $4\ 6\ 2$ 는 같은 모양을 만든다.

$N$ 개의 값으로 이루어진 하나의 삽입 순서로 정의된 BST가 주어진다. $1 \dots M$ 범위에서 고른 서로 다른 $N$ 개의 값으로 이루어진 삽입 순서 중에서, 이와 정확히 같은 모양의 트리를 만드는 것이 몇 가지인지 세어라. 이 개수는 매우 클 수 있으므로 $1{,}000{,}003$ 으로 나눈 나머지를 출력한다.

첫째 줄에 테스트 케이스의 수 $T$ ($T \le 100$) 가 주어진다.

각 테스트 케이스는 두 줄로 이루어진다. 첫째 줄에는 두 정수 $N$ 과 $M$ ($1 \le N \le M \le 1000$) 이 주어지며, 각각 트리의 노드 수와 값의 범위 크기를 뜻한다. 둘째 줄에는 트리의 모양을 정의하는 삽입 순서인 서로 다른 $N$ 개의 정수 $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 1000$) 이 주어진다.

각 테스트 케이스마다, $1 \dots M$ 범위의 값을 사용하여 같은 모양의 트리를 만드는 서로 다른 삽입 순서의 개수를 $1{,}000{,}003$ 으로 나눈 나머지를 한 줄에 출력한다.