P5110 Block Fast Recurrence

shadowice1984 found a problem: compute the $n$-th term of the Fibonacci sequence modulo $10^9+7$, where $n \leq 10^9$. shadowice1984 thought about it for a whole week but still could not solve it. Of course, that was when shadowice1984 had just started learning OI. Today, he learned fast matrix exponentiation and spent an entire day solving the problem above. He decided to make a problem to test your fast matrix exponentiation skills. To check whether the std he spent a week writing has any mistakes, he decided to ask you to help verify the problem.

Given a sequence $a$ that satisfies the recurrence $$a_{n}=233a_{n-1}+666a_{n-2},a_{0}=0,a_{1}=1$$ Compute the value of the $n$-th term of this sequence modulo $10^9+7$. There are $T$ queries in total. To reduce your input and output workload to some extent, we generate the queries using the following code: ```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

A single line with four integers, representing $T,SA,SB,SC$. After reading $T$, you can directly call `Mker::init()` to finish the input.

A single line with one integer, representing the bitwise XOR of all answers.

$SA,SB,SC$ are all within the range of the `unsigned long long` data type, so the returned $n$ is also within the range of the `unsigned long long` data type. The first 6 test points are worth $1$ point each. For test points 1 and 2, $T \leq 5000$. For test points 3, 4, 5, and 6, $T \leq 500000$. For all test points, $1 \leq T \leq 5×10^7$。 Translated by ChatGPT 5