Problem Description

Farmer Dongdong has been struggling with poor income recently. While pondering how to make more money, he overheard children next door discussing the problem of rabbit reproduction.

The problem is as follows: In the first month, there is a pair of newly born rabbits. After two months of growth, this pair of rabbits begins to give birth to a new pair at the start of every month from the third month onwards. The newly born rabbits, after two months of growth, can also give birth to a new pair every month. The question is, how many rabbits are there in the $n$-th month?

You might have noticed that the number of rabbits in the $n$-th month is exactly the $n$-th Fibonacci number. Although Dongdong does not understand what a Fibonacci number is, he has also discovered the pattern: the number of rabbits in the $(i+2)$-th month equals the number of rabbits in the $i$-th month plus the number of rabbits in the $(i+1)$-th month. The number of rabbits in the first few months is as follows:

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

Dongdong noticed that the number of rabbits grows faster as time goes on, and he is looking forward to making a fortune from raising rabbits. Therefore, he bought a pair of rabbits at the beginning of the first month to start raising them.

Every day, Dongdong feeds the rabbits. The rabbits have a peculiar eating habit: they always form circles of $k$ pairs each, and the remaining pairs that are less than $k$ form a circle. Starting from the third month, if there is only one pair of rabbits in a circle during feeding, these rabbits will die quickly due to their fear of loneliness.

We assume that the newly born rabbits always die. Thus, the number of rabbits each month can still be calculated. For example, when $k=7$, the number of rabbits in the first few months is as follows:

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

Given $n$, can you help Dongdong calculate how many pairs of rabbits he will have in the $n$-th month? Since the answer may be very large, you only need to tell Dongdong the remainder of the number of rabbit pairs in the $n$-th month divided by $p$.

Input Format

Input consists of a single line containing three positive integers $n, k, p$.

Output Format

Output a single line containing an integer, which represents the remainder of the number of rabbit pairs in the $n$-th month divided by $p$.

Sample Input and Output

Sample Input #1

6 7 100

Sample Output #1

7

Sample Input #2

7 7 5

Sample Output #2

2

Notes/Hints

For $100\%$ of the data, $1 \leq n \leq 10^{18}$, $2 \leq k \leq 10^6$, $2 \leq p \leq 10^9$.

见题面 Input 部分

见题面 Output 部分