P2020 [NOI2011] Rabbit Farmer

In recent years, Farmer Dongdong’s income has been poor. While he was worrying about how to make more money, he heard the kids next door discussing rabbit reproduction. The problem is as follows: At the beginning of the first month, there is one pair of newborn rabbits. After two months of growth, starting from the third month, this pair produces one new pair at the beginning of every month. A newborn pair will also be able to produce one new pair per month after two months of growth. How many rabbits are there in month $n$? You may have already noticed that the number of rabbits in month $n$ is exactly the $n$‑th Fibonacci number. Dongdong does not know what Fibonacci numbers are, but he also discovered the rule: the number of rabbits in month $i+2$ equals the number in month $i$ plus the number in month $i+1$. The numbers for the first few months are: $$1,1,2,3,5,8,13,21,34,\ldots$$ Dongdong found that the number of rabbits grows faster and faster, so he expected that raising rabbits would certainly make a lot of money. Thus, at the beginning of the first month, Dongdong bought one pair of rabbits and started breeding. Every day, Dongdong feeds the rabbits. Their feeding behavior is special: they always form circles of $k$ pairs; any remaining fewer than $k$ pairs also form one circle. Since rabbits are extremely afraid of loneliness, starting from the third month, if during feeding there is a circle with only one pair, that pair soon dies. We assume the ones that die are always the newborn rabbits, so the number of rabbits each month can still be computed. For example, when $k=7$, the numbers for the first few months are: $$1,1,2,3,5,7,12,19,31,49,80,\ldots$$ Given $n$, can you help Dongdong compute how many pairs of rabbits he has in month $n$? Since the answer can be very large, you only need to report the remainder of the number of pairs in month $n$ modulo $p$.

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

Output one line containing an integer, the remainder of the number of rabbit pairs in month $n$ modulo $p$.

| Test point ID | $n$ | $k,p$ | |:-:|:-:|:-:| | $1\sim 10$ | $1\leq n\leq 50$ | $2\leq k,p\leq1000$ | | $11$ | $1\leq n\leq 80$ | $2\leq k,p\leq 10^4$ | | $12,13$ | $1\leq n\leq 1000$ | $2\leq k,p\leq 10^4$ | | $14,15$ | $1\leq n\leq 10^6$ | $2\leq k,p\leq 10^6$ | | $16,17$ | $1\leq n\leq 10^{18}$ | $2\leq k,p\leq1000$ | | $18\sim 20$ | $1\leq n\leq 10^{18}$ | $2\leq k\leq 10^6$，$2\leq p\leq 10^9$ | For $100\%$ of the testdata, $1\leq n\leq 10^{18}$, $2\leq k\leq 10^6$, $2\leq p\leq 10^9$. Translated by ChatGPT 5