Description#

农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。 问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第n个月有多少只兔子？

聪明的你可能已经发现，第n个月的兔子数正好是第n个Fibonacci(斐波那契)数。栋栋不懂什么是Fibonacci数，但他也发现了规律：第i+2个月的兔子数等于第i个月的兔子数加上第i+1个月的兔子数。前几个月的兔子数依次为： 1 1 2 3 5 8 13 21 34 … 栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。 每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每k对兔子围成一圈，最后剩下的不足k对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。 我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当k=7时，前几个月的兔子数依次为： 1 1 2 3 5 7 12 19 31 49 80 … 给定n，你能帮助栋栋计算第n个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第n个月的兔子对数除p的余数即可。

Input#

输入一行，包含三个正整数n, k, p。

Output#

输出一行，包含一个整数，表示栋栋第n个月的兔子对数除p的余数。

Sample Input#

6 7 100

Sample Output#

7

HINT#

$1<=N<=10^18$ $2<=K<=10^6$ $2<=P<=10^9$

题解#

暴力75 暴力给的很足 可是后面的25分死一样难拿

我们可以以%7为例打一个表 如果以 减1为0 为分界那么会出现这样的情况

1, 1, 2, 3, 5, 0, 5, 5, 3, 0, 3, 3, 6, 2, 0, 2, 2, 4, 6, 3, 2, 5, 0, 5, 5, 3, 0, 3, 3, 6, 2, 0, ·········

那么我们会发现他用2个性质

1. 我们发现，每段开头必为相同的两数，并且它们恰是上一段的最末一位非0数；由于总共只有k−1种余数，所以不超过k段就会出现循环（如果有的话）。
2. 设开头的数为x 那么这个数列为%k意义下的斐波那契数列

我们发现在最后一个数变为0前
$x*f[len] \equiv 1 (mod k)$ 那么f[len]为x在模k意义下的逆元
所以，我们可以通过exgcd或者扩展欧拉定理，来快速求出f[len]。 如果没有逆元直接斐波那契数列矩阵快速幂过去就可以了

然后我们需要len 其实这个我们可以预处理出来vis
每次查询即可

最后由 $x*f[len-1]$ 得下一段的开头

有一个很强的结论：斐波那契数列在模k意义下一定是以0 1 1……为开头的循环，并且循环节长度<=6*k，所以暴力算vis就可以了

然后我们需要行内的转移矩阵 $\begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}$

行间的转移矩阵

$\begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -1 & 0 & 1 \end{bmatrix}$

什么你问我代码？ 我也没打出来啊。。。。。