Farmer Dongdong has been struggling with his income recently. While worrying about how to make some money, he heard his neighbor discussing the problem of rabbit breeding.

The problem is as follows: At the beginning of the first month, there is one newborn pair of rabbits. After growing for two months, these rabbits start to produce one new pair of rabbits at the beginning of each month starting from the third month. Each newly born pair of rabbits also takes two months to grow before they can produce one new pair of rabbits each month. How many pairs of rabbits are there in the $n$-th month?

As a clever person, you may have already discovered that the number of rabbit pairs in the $n$-th month is exactly the $n$-th Fibonacci number. Dongdong does not know what Fibonacci numbers are, but he has also discovered the pattern: the number of rabbit pairs in the $(i+2)$-th month is equal to the number of rabbit pairs in the $i$-th month plus the number of rabbit pairs in the $(i+1)$-th month. The number of rabbit pairs for the first few months is: $1, 1, 2, 3, 5, 8, 13, 21, 34, \dots$

Dongdong noticed that the number of rabbits grows faster and faster, and he expects that raising rabbits will definitely make money. So, at the beginning of the first month, Dongdong bought one pair of rabbits to raise.

Every day, Dongdong has to feed the rabbits. The rabbits are very special when eating; they always form groups of $k$ rabbits. Any remaining rabbits fewer than $k$ cannot form a group. Because rabbits are very afraid of being lonely, starting from the third month, if there is only one pair of rabbits left in a group during feeding, this pair of rabbits will die very quickly.

We assume that the ones that die are always the newborn rabbits, so the number of rabbit pairs for each month can still be calculated. For example, when $k=7$, the number of rabbit pairs for the first few months is: $1, 1, 2, 3, 5, 7, 12, 19, 31, 49, 80, \dots$

Given $n$, can you help Dongdong calculate how many pairs of rabbits he has in the $n$-th month? Since the answer can 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

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

Output

Output a single integer representing the remainder of the number of rabbit pairs in the $n$-th month divided by $p$.

Examples

Input 1

6 7 100

Output 1

7

Input 2

7 75

Output 2

2

Constraints

The range and characteristics of all test data are shown in the table below: