Rabbit Farming

Time limit1sMemory limit512 MB

Summary

Count rabbit pairs in month n modulo p, where Fibonacci-style growth loses one pair whenever the total leaves remainder 1 when divided by k.

Level: Hard8 of 10
Topics: Matrix, Number theory, Simulation
Solved: No attempts yet

Problem

Farmer DongDong's crop yield has been sluggish all year. While he worries about how to earn more money, he overhears the kids next door discussing rabbit breeding.

The question goes like this. At the start of the first month, a pair of newborn bunnies is born. After two months of growing up, these rabbits give birth to two new bunnies every month, starting at the start of the third month. The newborn bunnies grow up for two months, and after that they give birth to a pair of bunnies every month. The kids ask how many pairs of rabbits there are in the $n$ th month.

You have probably already noticed that the number of pairs in month $n$ is the $n$ th Fibonacci number. DongDong does not know what a Fibonacci number is, but he did notice the rule: the number of pairs in month $i+2$ equals the number of pairs in month $i$ plus the number of pairs in month $i+1$ . So the pairs in the first few months are 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

DongDong notices that the further he goes, the faster the number of rabbits grows. Hoping to make big money by breeding rabbits, he buys a pair of bunnies at the start of the first month.

Every day, DongDong feeds the rabbits. Rabbits are very particular about their feeding habits. There are always $k$ pairs of rabbits sitting in a circle. The remaining group, which has fewer than $k$ pairs, forms its own circle, because rabbits are very scared of loneliness. Starting from the third month, if a circle during feeding consists of only a single pair of rabbits, that pair dies off quickly. The rabbits that die are always the newest born. For example, when $k=7$ , the number of pairs in the first few months is 1, 1, 2, 3, 5, 7, 12, 19, 31, 49, 80, ...

Given $n$ , calculate the number of pairs of rabbits in month $n$ . The answer can be very large, so report it modulo $p$ .

Input

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

Output

A single line containing the number of pairs of rabbits in month $n$ , modulo $p$ .

Constraints

$1 \le n \le 10^{18}$
$2 \le k \le 10^{6}$ , $2 \le p \le 10^{9}$

Examples2

Example 1
Input
```
6 7 100
```
Expected output
```
7
```
Example 2
Input
```
7 7 5
```
Expected output
```
2
```