Generalized Fibonacci Numbers#4806
Generalized Fibonacci numbers F_n^{(k)} are defined as the following sequence:
Your task is to compute the remainder of dividing F_n^{(k)} by .
The input file contains three integers: , and (1 \leq n, k \leq 10^6, 2 \leq p \leq 10^9).
Output F_n^{(k)} \bmod p to the output file.
Example 1