分数: 1200 点
问题陈述
查找可能的序列元组的数量 (A_0,A_1,...,A_N) 满足以下所有条件,模 M:
- 对于每个 i (0\leq i\leq N), A_i 是一个长度序列 i 由之间的整数组成 1 和 K (含);
- 对于每个 i (1\leq i\leq N), A_{i-1} 是以下序列的子序列 A_i,即存在 1\leq x_i\leq i 这样就可以删除 x_i- 第一个元素 A_i 将导致序列等于 A_{i-1};
- 对于每个 i (1\leq i\leq N), A_i 按字典顺序大于 A_{i-1}.
约束
- 1 \leq N,K \leq 300
- 2 \leq M \leq 10^9
- N, K 和 M 是整数。
输入
输入由标准输入按以下格式给出:
N K M
输出
打印可能的序列元组的数量 (A_0,A_1,...,A_N),模数 M.
示例输入 1
2 2 100
示例输出 1
5
以下五元组满足条件:
- (),(1),(1,1)
- (),(1),(1,2)
- (),(1),(2,1)
- (),(2),(2,1)
- (),(2),(2,2)
示例输入 2
4 3 999999999
示例输出 2
358
示例输入 3
150 150 998244353
示例输出 3
186248260