#P2020. [NOI2011] 兔农

    ID: 1041 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学2011NOI 系列斐波那契Fibonacci逆元

[NOI2011] 兔农

题目描述

农夫栋栋近年收入不景气,正在他发愁如何能多赚点钱时,他听到隔壁的小朋友在讨论兔子繁殖的问题。

问题是这样的:第一个月初有一对刚出生的小兔子,经过两个月长大后,这对兔子从第三个月开始,每个月初生一对小兔子。新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 nn 个月有多少只兔子?

聪明的你可能已经发现,第 nn 个月的兔子数正好是第 nn 个 Fibonacci(斐波那契)数。栋栋不懂什么是 Fibonacci 数,但他也发现了规律:第 i+2i+2 个月的兔子数等于第 ii 个月的兔子数加上第 i+1i+1 个月的兔子数。前几个月的兔子数依次为:

1,1,2,3,5,8,13,21,34,1,1,2,3,5,8,13,21,34,\ldots

栋栋发现越到后面兔子数增长的越快,期待养兔子一定能赚大钱,于是栋栋在第一个月初买了一对小兔子开始饲养。

每天,栋栋都要给兔子们喂食,兔子们吃食时非常特别,总是每 kk 对兔子围成一圈,最后剩下的不足 kk 对的围成一圈,由于兔子特别害怕孤独,从第三个月开始,如果吃食时围成某一个圈的只有一对兔子,这对兔子就会很快死掉。

我们假设死去的总是刚出生的兔子,那么每个月的兔子数仍然是可以计算的。例如,当 k=7k=7 时,前几个月的兔子数依次为:

1,1,2,3,5,7,12,19,31,49,80,1,1,2,3,5,7,12,19,31,49,80,\ldots

给定 nn,你能帮助栋栋计算第 nn 个月他有多少对兔子么?由于答案可能非常大,你只需要告诉栋栋第 nn 个月的兔子对数除 pp 的余数即可。

输入格式

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

输出格式

输出一行,包含一个整数,表示栋栋第 nn 个月的兔子对数除 pp 的余数。

6 7 100
7
7 7 5
2

提示

测试点编号 nn k,pk,p
1101\sim 10 1n501\leq n\leq 50 2k,p10002\leq k,p\leq1000
1111 1n801\leq n\leq 80 2k,p1042\leq k,p\leq 10^4
12,1312,13 1n10001\leq n\leq 1000
14,1514,15 1n1061\leq n\leq 10^6 2k,p1062\leq k,p\leq 10^6
16,1716,17 1n10181\leq n\leq 10^{18} 2k,p10002\leq k,p\leq1000
182018\sim 20 2k1062\leq k\leq 10^62p1092\leq p\leq 10^9

对于 100%100\% 的数据,1n10181\leq n\leq 10^{18}2k1062\leq k\leq 10^62p1092\leq p\leq 10^9