Fibonacci Combination Sum Modulo

Given three integers n, k, and p, where p is a prime number satisfying p mod k = 1, compute the following expression modulo p:

$$\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor} \binom{n}{i\times k}\times F_{i\times k} $$

Here, the combination number is defined by $$\binom{n}{r} = \frac{n!}{r!(n-r)!},$$ and the Fibonacci sequence \(F_n\) is defined as follows:

• \(F_0 = 1, F_1 = 1\)
• For \(n \ge 2\), \(F_n = F_{n-1} + F_{n-2}\)

Your task is to calculate the sum modulo p.

inputFormat

The input consists of a single line containing three space-separated integers n, k, and p.

Note: It is guaranteed that p is prime and p mod k = 1.

outputFormat

Output a single integer representing the value of the expression modulo p.

sample

5 2 7

4