/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 650 点
問題文
整数 A,B,M が与えられます。
(1,2,\ldots,AB-1) の順列 P=(P_1,\ldots,P_{AB-1}) であって、以下の条件を全て満たすものは何通りありますか？個数を M で割ったあまりを求めてください。
- P の最長増加部分列の長さは A
- P の最長減少部分列の長さは B
- 整数 n であって、P の末尾に n+0.5 を追加しても最長増加部分列の長さも最長減少部分列の長さも変化しないようなものが存在する
制約
- 入力される数値は全て整数
- 2\leq A,B
- AB\leq 120
- 10^8\leq M\leq 10^9
- M は素数
入力
入力は以下の形式で標準入力から与えられる。
A B M
出力
条件を満たす順列の個数を M で割ったあまりを出力せよ。
入力例 1
3 2 998244353
出力例 1
10
例えば、P=(2,4,5,1,3) は条件を満たします。これは以下のようにして確認できます。
- P の最長増加部分列の長さは 3
- P の最長減少部分列の長さは 2
- n=4 とすると、(2,4,5,1,3,4.5) の最長増加部分列の長さは 3 かつ最長減少部分列の長さは 2
条件を満たす (1,2,3,4,5) の順列は 10 通りです。
入力例 2
10 12 924844033
出力例 2
623378361
個数を M で割ったあまりを出力してください。
Score : 650 points
Problem Statement
You are given integers A, B, and M.
How many permutations P = (P_1, \dots, P_{AB-1}) of (1, 2, \ldots, AB - 1) satisfy all of the following conditions? Find the count modulo M.
- The length of a longest increasing subsequence of P is A.
- The length of a longest decreasing subsequence of P is B.
- There exists an integer n such that appending n + 0.5 to the end of P does not change either of the lengths of a longest increasing subsequence and a longest decreasing subsequence.
Constraints
- All input values are integers.
- 2 \leq A, B
- AB \leq 120
- 10^8 \leq M \leq 10^9
- M is a prime.
Input
The input is given from Standard Input in the following format:
A B M
Output
Print the number of permutations satisfying the conditions, modulo M.
Sample Input 1
3 2 998244353
Sample Output 1
10
For example, P = (2, 4, 5, 1, 3) satisfies the conditions. This can be confirmed as follows:
- The length of a longest increasing subsequence of P is 3.
- The length of a longest decreasing subsequence of P is 2.
- For n = 4, the lengths of longest increasing and decreasing subsequences of (2, 4, 5, 1, 3, 4.5) are 3 and 2, respectively.
There are 10 permutations of (1, 2, 3, 4, 5) that satisfy the conditions.
Sample Input 2
10 12 924844033
Sample Output 2
623378361
Print the count modulo M.