Modified Fibonacci Rabbits

Farmer Dongdong once heard the children next door discussing the reproduction of rabbits. Traditionally, the rabbit pairs follow a Fibonacci‐like progression: at the beginning of month 1 there is 1 pair and at the beginning of month 2 there is also 1 pair. From the third month on, every mature pair (aged at least 2 months) produces a new pair at the beginning of each month. Thus, without interference, the number of rabbit pairs in the first few months are

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

However, the rabbits have a peculiar feeding behavior. Every day they form circles: exactly every k pairs form a complete circle, and the remaining (if any) form another circle. Since rabbits are very afraid of being alone, starting from the third month, if any circle ends up having exactly one pair, that lone pair dies quickly. We assume that the death always occurs from the newly born rabbits of that month.

Thus, if we define \(A(n)\) as the number of rabbit pairs at the beginning of month \(n\), we have:

• \(A(1)=1\)
• \(A(2)=1\)
• For \(n\ge 3\): \[ \text{Let } S=A(n-1)+A(n-2). \quad \text{Then, if } S\equiv1 \; (\bmod\; k)\text{, set } A(n)=S-1, \text{ otherwise } A(n)=S. \]

For example, when \(k=7\) the sequence becomes:

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

Your task is: given three integers \(n\), \(k\), and \(p\), compute \(A(n)\bmod p\). (Note that \(n\) is the month number, \(k\) is the group size for feeding, and \(p\) is the modulus.)

inputFormat

The input consists of a single line containing three space‐separated integers \(n\), \(k\), and \(p\), where \(n\) (\(n\ge1\)) is the month number, \(k\) (\(k\ge2\)) is the group size, and \(p\) is a positive integer modulus.

outputFormat

Output a single integer: the number of rabbit pairs in month \(n\) modulo \(p\).

sample

6 7 100

7