#P1238. 【挑战题】染色
【挑战题】染色
题目描述
禾木收到了一张纸带,纸带上有 n 个位置。现在他想把这个纸带染色,他一共有 m 种颜色,每个位置都可以染任意颜色,但是他发现如果某连续 m 个位置被染成了 m 种不同的颜色,那么就不美观,于是他决定让任意的相邻 m 个位置的颜色至少有两个位置相同。他想知道一共有多少种染色的方案,并输出方案数 mod p 的结果。
输入格式
共 1 行包含三个正整数 n,m,p。
输出格式
1行,包含一个整数,表示答案对 p 取模的结果。
样例1
4 2 10
2
样例解释
只有全染 颜色1 或者全染 颜色2 两种情况。
样例2
4 3 10
1
数据范围
1 ≤ n, m ≤ 5000; 2 ≤ p ≤ 10⁹。