P10664 BZOJ3328 PYXFIB

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)$.

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 $T$ lines, each containing one integer, which is the result.

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