金星小巴（简单版）

• 时间限制：3 秒
• 内存限制：256 MiB

题目描述

一张车票由 $n$ 个 $k$ 进制数字组成，即一个长度为 $n$、每项属于 $[0,k-1]$ 的序列。

若票面上存在某一位数字，等于其余所有数字之和对 $k$ 取模的结果，则称这张票是幸运的。例如 $k=10$ 时，$7135$ 是幸运的，因为 $7+1+5\equiv3\pmod {10}$。

求幸运车票的总数对质数 $m$ 取模后的结果。

输入格式

输入一行三个整数 $n,k,m$，其中 $m$ 为质数。

输出格式

输出一个整数，表示幸运车票数量对 $m$ 取模的结果。

样例输入 1

3 2 1000000007

样例输出 1

4

样例输入 2

3 4 1000000007

样例输出 2

28

数据范围

对于所有数据：$1\le n\le100$，$1\le k\le30$，$10^8\le m\le10^9+7$，且 $m$ 为质数。

提示

第一组样例的四张幸运车票为 $000,011,101,110$。