B. 染色

题目描述

小W收到了一张纸带，纸带上有 $n$ 个位置。现在他想把这个纸带染色，他一共有 $m$ 种颜色，每个位置都可以染任意颜色，但是他发现如果某连续 $m$ 个位置被染成了 $m$ 种不同的颜色，那么就不美观，于是他决定让任意的相邻 $m$ 个位置的颜色至少有两个位置相同。他想知道他一共有多少种染色的方案。

输入格式

第一行三个整数 $n$，$m$，$p$。

输出格式

输出一行一个整数，表示答案对 $p$ 取模的结果。

样例1

input

4 2 10

output

2

explanation

只有全染 $1$ 或者全染 $2$ 两种情况。

样例2

input

4 3 10

output

1

限制与约定

对于 $10\%$ 的数据，$n, m \le 8$。

对于另外 $15\%$ 的数据，$m \le 10$。

对于另外 $5\%$ 的数据，$n < m$。

对于另外 $30\%$ 的数据，满足 $n, m \le 300$。

对于 $100\%$ 的数据，$n, m \le 5000$，$2 \le p \le 10^9$。

时间限制：2s

空间限制：512MB

下载

样例数据下载