National Olympiad in Informatics, China, 2011

Farmer DongDong's crop yield has been sluggish all year long. Just when he's stressing over how to make some more money, he overheard the kids next door discussing the issue of rabbit breeding.

The question is this: A pair of little bunnies were just born at the start of the first month. After growing up in two months, these rabbits will give birth to two new little bunnies every month starting at the start of the third month. The newborn bunnies, after two months of growing up, will themselves give birth to a pair of bunnies every month afterwards. So the kids ask, how many total pairs of rabbits will there be in the $n$th month?

Being so clever, you've probably already discovered that the number of pairs of rabbits in month $n$ just happens to be the $n$th Fibonacci number. DongDong doesn't know what a Fibonacci number is, but he did notice the rule: the pairs of rabbits in month $i+2$ is equal to the pairs of rabbits in month $i$ plus the pairs of rabbits in month $i+1$. Thus, the pairs of rabbits in the first few months are: $1,1,2,3,5,8,13,21,34,\dots$

DongDong noticed that the further he goes, the faster the number of rabbits grow. Looking forward to making big bucks breeding rabbits, DongDong immediately went out and bought a pair of bunnies at the start of the first month.

Each day, DongDong will feed the rabbits. Rabbits are very particular about their feeding habits. There will always be $k$ pairs of rabbits surrounded in a circle. The remaining group which falls short of $k$ pairs will form a circle, for rabbits are very scared of loneliness. Starting from the third month, if there exists a circle during feeding which consists of only a single pair of rabbits, then this pair will quickly die off.

Assuming that the rabbits who die are always the newest born, then the number of rabbits can still be calculated. For instance, when $k=7$, the number of pairs of rabbits in the first few months will be: $1,1,2,3,5,\mathbf{\text{7}},12,19,31,\mathbf{\text{49}},80,\dots$

Given $n$, can you help DongDong calculate how many pairs of rabbits there will be in month $n$? Since the answer can be very large, you are only required to report this number modulo $p$.

Input Specification

A single line containing three positive integers $n$, $k$, and $p$.

Output Specification

Output a single line containing a single integer, representing the number of pairs of rabbits in month $n$, modulo $p$.

Sample Input 1

6 7 100

Sample Output 1

7

Sample Input 2

7 7 5

Sample Output 2

2

Constraints

The attributes of all the test cases are outlined below.

Test Case	Range of $n$	Range of $k$ and $p$
$1$	$1\le n\le 50$	$2\le k,p\le 1000$
$2$
$3$
$4$
$5$
$6$
$7$
$8$
$9$
$10$
$11$	$1\le n\le 80$	$2\le k,p\le 10000$
$12$	$1\le n\le 1000$	$2\le k,p\le 10000$
$13$
$14$	$1\le n\le {10}^6$	$2\le k,p\le {10}^6$
$15$
$16$	$1\le n\le {10}^{18}$	$2\le k,p\le 1000$
$17$
$18$	$1\le n\le {10}^{18}$	$2\le k\le {10}^6,2\le p\le {10}^9$
$19$
$20$

Problem translated to English by Alex.