카르테시안 트리

서로 다른 정수로 이루어진 수열 $A$ 하나에서 카르테시안 트리가 유일하게 정해진다. 카르테시안 트리는 다음 네 조건을 만족하는 트리이다.

1. 루트가 있는 이진 트리이다.
2. 각 노드는 $A$의 원소 하나에 대응한다.
3. 트리를 인오더로 순회하면 $A$와 순서가 같다.
4. 부모 노드의 값이 자식 노드의 값보다 작다. 즉 최소 힙이다.

아래 그림은 $A = [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]$로 만든 카르테시안 트리이다.

수열 $A$로 만든 카르테시안 트리를 $T$라고 하자. $T$의 점수는 이렇게 구한다. 자식이 두 개인 노드마다 두 자식의 값이 $A$에서 놓인 위치를 찾고, 두 위치의 차이를 구한다. 이 차이를 그런 노드 전체에서 더한 값이 $T$의 점수이다.

위 그림에서 자식이 두 개인 노드는 1, 3, 10, 15이다. 노드 1의 두 자식은 3과 5이고 $A$에서 각각 2번째와 11번째에 있으므로 이 노드의 점수는 $11 - 2 = 9$이다. 나머지 세 노드의 점수는 각각 2, 3, 2이므로 $T$의 점수는 $9 + 2 + 3 + 2 = 16$이다.

$N$, $S$, $\text{MOD}$가 주어진다. $1$부터 $N$까지의 수로 이루어진 순열은 모두 $N!$개이고, 각 순열은 카르테시안 트리를 하나씩 만든다. 점수가 $S$ 이하인 트리의 개수를 $X$라고 할 때, $X$를 $\text{MOD}$로 나눈 나머지를 출력하는 프로그램을 작성하시오.

첫째 줄에 $N$, $S$, $\text{MOD}$가 공백으로 구분되어 주어진다. ($1 \le N \le 100$, $0 \le S \le 100$, $3 \le \text{MOD} \le 10^9$, $\text{MOD}$는 소수)

첫째 줄에 $N!$개의 순열 중에서 트리의 점수가 $S$ 이하인 것의 개수를 $\text{MOD}$로 나눈 나머지를 출력한다.

$N = 3$일 때 순열 $(2, 1, 3)$과 $(3, 1, 2)$의 점수는 2이고, 나머지 네 순열의 점수는 0이다.