UOJ Logo

NOI.AC

2S 512MB

#37. 染色

Statistics

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

下载

样例数据下载