配点 : 101 点
問題文
Kemuniku 对连胜次数感兴趣,提出了以下问题。
最大连胜问题
正整数 N, M 和长度 N 序列 W, L 。
W_i = x 在 i \ (1 \le i \le N) 和“ i \lt j \le N 和 所有满足 L_j = x 在 j 不存在。” i 的数量 比方说 f(x) 。
此时 查找 \displaystyle \max_{1 \le x \le M} f(x) 。但是,给定的序列 W, L 关于 1 \le W_i, L_i \le M 和 W_i \ne L_i 保证持有。
不过哈鲁伦觉得这道题太简单了,于是他想到了下一道题。
许多最大连胜问题
长度是 套装 N 序列 W, L 一群 最大连胜问题 的所有可能输入是 \big ( M \times (M - 1) \big ) ^ N 方法有很多。
关于所有这些 最大连胜问题 的答案总和 除以 P 后求余数。 请解决
许多最大连胜问题 。
制約
- 1 \le N \le 300
- 2 \le M \le 300
- 10^8 \le P \le 10^9
- P 是质数
- 输入全为整数。
部分点
针对此问题设置了部分分数。
- N, M \le 30 的数据集 1 点。 如果您正确回答
入力
输入将以以下格式从标准输入提供。
N \ M \ P
出力
打印答案。
入力例 1
2 2 998244353
出力例 1
6
最大连胜问题 的可能输入 (W, L) 如下 4 没错。
- ((1, 1),(2, 2)) 那么答案是 2
- ((1, 2),(2, 1)) 那么答案是 1
- ((2, 1),(1, 2)) 那么答案是 1
- ((2, 2),(1, 1)) 那么答案是 2
,所以答案是 6 。
入力例 2
7 7 202602157
出力例 2
123958978
入力例 3
46 35 924844033
出力例 3
88210081