/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
整数 N, M が与えられます。次の条件を満たす長さ N の列 A=[A_1, A_2, \ldots, A_N] の個数を求めてください。
- 2 \le A_i \le M (1 \leq i \leq N)
- 1 から N までの整数の順列 P=[P_1,P_2,\ldots,P_N] であって次の性質を持つものが存在する。
- 1 から N までの各 i について、A_i は列 [P_1, P_2, \ldots, P_{i-1}, P_{i+1}, \ldots, P_{N-1}, P_N] の最長増加部分列の長さに等しい。
この個数は非常に大きい可能性があるため、これを素数 Q で割った余りを出力してください。
制約
- 3 \le N \le 5000
- 2 \le M \le N-1
- 10^8 \le Q \le 10^9
- Q は素数である。
入力
入力は以下の形式で標準入力から与えられる。
N M Q
出力
答えを Q で割った余りを出力せよ。
入力例 1
3 2 686926217
出力例 1
1
このような列は [2, 2, 2] のみです。ここで [1, 2, 3] という順列が存在して性質を満たします。
入力例 2
4 3 354817471
出力例 2
9
このような列は次の 9 個です: [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 3, 3], [2, 3, 2, 2], [2, 3, 3, 2], [3, 2, 2, 2], [3, 3, 2, 2], [3, 3, 3, 3]。
入力例 3
5 2 829412599
出力例 3
1
このような列は [2, 2, 2, 2, 2] のみです。
入力例 4
5 3 975576997
出力例 4
23
入力例 5
69 42 925171057
出力例 5
801835311
Score : 900 points
Problem Statement
You are given integers N and M. Find the number of arrays A=[A_1, A_2, \ldots, A_N] of length N such that the following conditions hold:
- 2 \le A_i \le M (1 \leq i \leq N)
- There exists a permutation P=[P_1,P_2,\ldots,P_N] of integers from 1 to N with the following property:
- For every i from 1 to N, A_i equals the length of the longest increasing subsequence of the sequence [P_1, P_2, \ldots, P_{i-1}, P_{i+1}, \ldots, P_{N-1}, P_N].
As this number can be very large, output it modulo some prime Q.
Constraints
- 3 \le N \le 5000.
- 2 \le M \le N-1.
- 10^8 \le Q \le 10^9
- Q is a prime.
Input
Input is given from Standard Input in the following format:
N M Q
Output
Print the answer modulo Q.
Sample Input 1
3 2 686926217
Sample Output 1
1
The only such array is [2, 2, 2], for which exists a permutation [1, 2, 3].
Sample Input 2
4 3 354817471
Sample Output 2
9
There are 9 such arrays: [2, 2, 2, 2], [2, 2, 2, 3], [2, 2, 3, 2], [2, 2, 3, 3], [2, 3, 2, 2], [2, 3, 3, 2], [3, 2, 2, 2], [3, 3, 2, 2], [3, 3, 3, 3].
Sample Input 3
5 2 829412599
Sample Output 3
1
The only such array is [2, 2, 2, 2, 2].
Sample Input 4
5 3 975576997
Sample Output 4
23
Sample Input 5
69 42 925171057
Sample Output 5
801835311