← 返回题目列表

AtCoder · agc024_e

E. 序列变得越来越困难

中文机器翻译题面 查看原题

分数: 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