Problem Description

Given integers $n, k, p$, compute the value of the following expression modulo $p$:

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

Where:

• $p$ is a prime number, and the remainder of $p$ divided by $k$ is $1$.
• $C$ denotes the binomial coefficient, i.e. $C_n^m=\frac{n!}{m!(n-m)!}$.
• $F_n$ denotes the Fibonacci sequence, i.e. $F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}(n\geq 2)$.

Input Format

The first line contains a positive integer $T$, the number of test cases.

The next $T$ lines each contain three positive integers $n, k, p$.

Output Format

Output $T$ lines, each containing one integer, which is the result.

1
1 2 3

1

Hint

For $100\%$ of the testdata, it is guaranteed that $1\leq n\leq 10^{18}$, $1\leq k \leq 20000$, $1\leq T\leq 20$, $1\leq p\leq 10^9$, $p$ is a prime number, and the remainder of $p$ divided by $k$ is $1$.

Translated by ChatGPT 5