种花
题目描述
现在有一行花田,共有n个可以种花的位置,我们有m种不同的花, 每种各一束
规定种花时两棵花不能种在相邻位置
求种花的方案总数(全部都要种下)
如果种花的位置不同或者至少一个位置种的花种类不同,就认为两个方案是不同的
由于答案可能很大,所以输出结果对q取模
输入
输入一行,共3个整数n,m,q
输出
输出一个整数,表示种花方案数,输出结果对q取模
输入样例
3 2 10007
输出样例
2
数据范围与限制
对于50%的数据,有\(n\leq3000,m\leq1500\)
对于80%的数据,保证q为质数
对于100%的数据有\(n\leq200000,1\leq m \leq100000,1\leq q\leq10^9,m\leq\lceil \frac{n}{2} \rceil\)
时间限制1s,空间限制256m
