P9510 『STA - R3』High-Dimensional Hypercube

The Fibonacci sequence is defined as follows: $$\operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases}$$ Now we define a function (note that when $n

**This problem contains multiple test cases**. The first line contains an integer $T$, the number of test cases. For each test case, a line contains two integers $n,p$.

For each test case, output one integer per line, the result modulo $p$.

Sample explanation: For the first test case, $1\times(0+1^2+1)+1\times(0+1^2+1)=4$. For the second test case, $1\times(0+1^2+1)+1\times(0+1^2+1)+2\times(1+2^2+2)=18$. ### Constraints **This problem uses bundled tests.** - Subtask 1 (5 points): $n \le 10^7$, $p=10^9+7$. - Subtask 2 (20 points): $T\le 10^4$, $n \le 10^8$, $p=10^9+7$. - Subtask 3 (5 points): $p=2$. - Subtask 4 (15 points): $p\le 5$. - Subtask 5 (30 points): $T\le 10^4$, $n \le 10^8$. - Subtask 6 (25 points): no special constraints. For all testdata, $1\le T\le 2\times 10^5$, $1\le n\le 10^{18}$, $2\le p\le 10^9+7$。 Translated by ChatGPT 5