农夫栋栋近年收入不景气，正在他发愁如何能多赚点钱时，他听到隔壁的小朋友在讨论兔子繁殖的问题。
问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 n 个月有多少只兔子？
聪明的你可能已经发现，第 n 个月的兔子数正好是第 n 个 Fibonacci（斐波那契）数。栋栋不懂什么是 Fibonacci 数，但他也发现了规律：第 i+2 个月的兔子数等于第 i 个月的兔子数加上第 i+1 个月的兔子数。前几个月的兔子数依次为：
1,1,2,3,5,8,13,21,34,\ldots
栋栋发现越到后面兔子数增长的越快，期待养兔子一定能赚大钱，于是栋栋在第一个月初买了一对小兔子开始饲养。
每天，栋栋都要给兔子们喂食，兔子们吃食时非常特别，总是每 k 对兔子围成一圈，最后剩下的不足 k 对的围成一圈，由于兔子特别害怕孤独，从第三个月开始，如果吃食时围成某一个圈的只有一对兔子，这对兔子就会很快死掉。
我们假设死去的总是刚出生的兔子，那么每个月的兔子数仍然是可以计算的。例如，当 k=7 时，前几个月的兔子数依次为：
1,1,2,3,5,7,12,19,31,49,80,\ldots
给定 n，你能帮助栋栋计算第 n 个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第 n 个月的兔子对数除 p 的余数即可。
输入一行，包含三个正整数 n, k, p。
输出一行，包含一个整数，表示栋栋第 n 个月的兔子对数除 p 的余数。
6 7 100
7
7 7 5
2
| 测试点编号 | n | k,p |
|---|---|---|
| 1\sim 10 | 1\leq n\leq 50 | 2\leq k,p\leq1000 |
| 11 | 1\leq n\leq 80 | 2\leq k,p\leq 10^4 |
| 12,13 | 1\leq n\leq 1000 | 2\leq k,p\leq 10^4 |
| 14,15 | 1\leq n\leq 10^6 | 2\leq k,p\leq 10^6 |
| 16,17 | 1\leq n\leq 10^{18} | 2\leq k,p\leq1000 |
| 18\sim 20 | 1\leq n\leq 10^{18} | 2\leq k\leq 10^6，2\leq p\leq 10^9 |
对于 100\% 的数据，1\leq n\leq 10^{18}，2\leq k\leq 10^6，2\leq p\leq 10^9。
NOI