题目描述

禾木收到了一张纸带，纸带上有 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⁹。