/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
(1,2,\ldots,N) の順列を、以下では単に順列と呼びます。
二つの順列 A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N) にたいして、類似度 を以下の条件を満たす 1 以上 N-1 以下の整数 i の個数で定めます。
- (A_{i+1}-A_i)(B_{i+1}-B_i)>0
二つの順列の組 (A,B) であって、類似度が K であるものの個数を素数 P で割ったあまりを答えてください。
制約
- 2\leq N \leq 100
- 0\leq K \leq N-1
- 10^8 \leq P \leq 10^9
- P は素数
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K P
出力
答えを出力せよ。
入力例 1
3 1 282282277
出力例 1
16
例えば条件を満たす順列の組の一つとして、以下のものが考えられます。
- A=(1,2,3)
- B=(1,3,2)
この例では、(A_2 - A_1)(B_2 -B_1) > 0, (A_3 - A_2)(B_3 -B_2) < 0 であることから、A と B の類似度は 1 だとわかります。
入力例 2
50 25 998244353
出力例 2
131276976
個数を P で割ったあまりを答えてください。
Score : 600 points
Problem Statement
Below, a permutation of (1,2,\ldots,N) is simply called a permutation.
For two permutations A=(A_1,A_2,\ldots,A_N),B=(B_1,B_2,\ldots,B_N), let us define their similarity as the number of integers i between 1 and N-1 such that:
- (A_{i+1}-A_i)(B_{i+1}-B_i)>0.
Find the number, modulo a prime number P, of pairs of permutations (A,B) whose similarity is K.
Constraints
- 2\leq N \leq 100
- 0\leq K \leq N-1
- 10^8 \leq P \leq 10^9
- P is a prime number.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N K P
Output
Print the answer.
Sample Input 1
3 1 282282277
Sample Output 1
16
For instance, below is a pair of permutations that satisfies the condition.
- A=(1,2,3)
- B=(1,3,2)
Here, we have (A_2 - A_1)(B_2 -B_1) > 0 and (A_3 - A_2)(B_3 -B_2) < 0, so the similarity of A and B is 1.
Sample Input 2
50 25 998244353
Sample Output 2
131276976
Print the number modulo P.