P5110 块速递推

shadowice1984 发现了一道题：求斐波那契数列第 $n$ 项模 $10^9+7$ 的值，$n \leq 10^9$。 shadowice1984 想了一个星期可他还是不会做。 当然，这是 shadowice1984 刚学 OI 时候的事情了，今天他学习了矩阵快速幂并且花了一整天解决了上面的问题。 他决定出一道题来测试你的矩阵快速幂水平如何，为了检查他花了一个星期写出的 std 到底有没有错，他决定让你来帮他验题。

给定一个数列 $a$ 满足递推式 $$a_{n}=233a_{n-1}+666a_{n-2},a_{0}=0,a_{1}=1$$ 求这个数列第 $n$ 项模 $10^9+7$ 的值，一共有 $T$ 组询问。 为了在某种程度上减少你的输入和输出量，我们采用以下的代码来生成询问： ```C namespace Mker { unsigned long long SA,SB,SC; void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);} unsigned long long rand() { SA^=SA13,SA^=SA

无

无

$SA,SB,SC$ 均在 `unsigned long long` 数据类型的范围之内，由此可以发现返回的 $n$ 值也是 `unsigned long long` 数据类型的范围之内。 前 6 个测试点每个测试点 $1$ 分。 对于 1,2 测试点 $T \leq 5000$。 对于 3,4,5,6 测试点 $T \leq 500000$。 对于所有测试点 $1 \leq T \leq 5×10^7$。