[Noi2011]兔农

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

问题是这样的：第一个月初有一对刚出生的小兔子，经过两个月长大后，这对兔子从第三个月开始，每个月初生一对小兔子；新出生的小兔子生长两个月后又能每个月生出一对小兔子。问第 $n$ 个月有多少只兔子？

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

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

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

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

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

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

给定 $n$ ，你能帮助栋栋计算第 $n$ 个月他有多少对兔子么？由于答案可能非常大，你只需要告诉栋栋第 $n$ 个月的兔子对数除以 $p$ 的余数即可。

输入格式

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

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

6 7 100

$k=7$ 时前几个月的兔子对数依次为 $1, 1, 2, 3, 5, 7, \dots$ ，第 $6$ 个月为 $7$ 对，对 $100$ 取余仍为 $7$ 。

本题为 NOI 2011 试题「兔农」，题面与测试数据整理自 BZOJ 2432。

6 7 100