『STA - R3』高维立方体

如下定义斐波那契数列： $$\operatorname{fib}(n)=\begin{cases}1&n\le 2\\\operatorname{fib}(n-1)+\operatorname{fib}(n-2)&n>2\end{cases}$$ 现在我们定义一个函数（注意在 $n<1$ 时这个函数的值是 $0$）： $$f(n)=\sum_{i=1}^n\operatorname{fib}^2(i)$$ 由于求斐波那契数列的前缀和太简单了，你需要求出： $$\sum_{i=1}^n\operatorname{fib}(i)\cdot(f(i-2)+\operatorname{fib}^2(i)+\operatorname{fib}(i))$$ 的值，答案对输入的 $p$ 取模。 注：$\operatorname{fib}^2(x)$ 表示 $\operatorname{fib}(x)$ 的平方。

**本题有多组数据**。 第一行一个整数 $T$，表示数据的组数。 对于每组数据，一行两个整数 $n,p$。

对于每组数据，输出一行一个整数，表示答案对 $p$ 取模后的结果。

3
2 100
3 100
4 100

4
18
60

样例解释： 对于第一组数据，$1\times(0+1^2+1)+1\times(0+1^2+1)=4$。 对于第二组数据，$1\times(0+1^2+1)+1\times(0+1^2+1)+2\times(1+2^2+2)=18$。 ### 数据范围 **本题采用捆绑测试。** - 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）：无特殊限制。 对于所有数据，$1\le T\le 2\times 10^5$，$1\le n\le 10^{18}$，$2\le p\le 10^9+7$。