金星小巴车票（困难版）

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

题目描述

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

若车票上存在一个数字，等于其余所有数字之和对 $k$ 取模的结果，则称这张车票是幸运的。

求幸运车票的数量。答案可能很大，只需输出其对质数 $m$ 取模的结果。

输入格式

输入一行三个整数 $n,k,m$，分别表示车票位数、进制和答案模数。

输出格式

输出幸运车票数量对 $m$ 取模的结果。

样例输入 1

3 2 1000000007

样例输出 1

4

样例输入 2

3 4 1000000007

样例输出 2

28

数据范围

对于所有数据，$1\le n\le 10^{18}$，$1\le k\le 2000$，$10^8\le m\le 10^9+7$，且 $m$ 为质数。