카르테시안 트리 2

서로 다른 정수로 이루어진 수열 $A$가 주어지면, 이 수열로 만들 수 있는 카르테시안 트리는 하나뿐이다. 카르테시안 트리는 다음 네 조건을 지키는 트리이다.

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

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

수열 $A$로 만든 카르테시안 트리를 $T$라고 하자. $T$의 점수는 이렇게 계산한다. 자식이 둘인 노드를 모두 찾은 뒤, 그런 노드마다 두 자식에 저장된 값이 $A$에서 놓인 인덱스의 차이를 구하고, 그 차이를 전부 더한다. 인덱스는 0부터 센다.

위 그림에서 자식이 둘인 노드는 1, 3, 10, 15이다. 노드 1의 두 자식은 3과 5이고 $A$에서 두 값의 인덱스는 각각 1과 10이므로, 이 노드의 점수는 $10 - 1 = 9$이다. 나머지 세 노드의 점수는 각각 2, 3, 2이므로 $T$의 점수는 $9 + 2 + 3 + 2 = 16$이다.

$N$과 $MOD$가 주어진다. $1$부터 $N$까지의 수로 이루어진 순열은 $N!$개이고, 순열마다 카르테시안 트리가 하나씩 만들어진다. 이렇게 만들어지는 모든 카르테시안 트리의 점수를 더한 값을 $X$라고 할 때, $X$를 $MOD$로 나눈 나머지를 출력하는 프로그램을 작성하시오.

첫째 줄에 $N$과 $MOD$가 공백을 사이에 두고 주어진다. ($1 \le N \le 100$, $3 \le MOD \le 10^9$, $MOD$는 소수)

첫째 줄에 $N!$개의 순열로 만든 모든 카르테시안 트리의 점수의 합을 $MOD$로 나눈 나머지를 출력한다.