Background

shadowice1984 came across a problem: to find the value of the nth term of the Fibonacci sequence modulo \(10^9+7\), where \(n \leq 10^9\).

shadowice1984 pondered over it for a week but couldn't solve it.

Of course, that was when shadowice1984 was just starting out in OI. Today, he has learned about matrix exponentiation and spent a whole day solving the aforementioned problem.

He decided to create a problem to test your proficiency in matrix exponentiation. To verify if the standard solution he spent a week writing is correct, he wants you to help him with the verification.

Problem Description

Given a sequence \(a\) that satisfies the recurrence relation

\[a_n = 233a_{n-1} + 666a_{n-2}, a_0 = 0, a_1 = 1\]

calculate the value of the nth term of this sequence modulo \(10^9+7\), for \(T\) queries.

To reduce the amount of input and output, we use the following code to generate the queries:

namespace Mker
{
    unsigned long long SA,SB,SC;
    void init(){scanf("%llu%llu%llu",&SA,&SB,&SC);}
    unsigned long long rand()
    {
        SA^=SA<<32,SA^=SA>>13,SA^=SA<<1;
        unsigned long long t=SA;
        SA=SB,SB=SC,SC^=t^SA;return SC;
    }
}

After calling the Mker::init() function, the random number generator will start working. The value returned by the \(i\)-th call to Mker::rand() function is the \(n\) value for the \(i\)-th query.

To reduce the amount of output, you only need to output the XOR sum of all the answers.

Input Format

A single line with four integers, representing the values of \(T, SA, SB, SC\). You can call Mker::init() immediately after reading \(T\) to complete the input.

Output Format

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

Sample Input and Output

Sample Input #1

4779 17790102303135 73152356900611 22086182463002

Sample Output #1

391030355

Sample Input #2

49999561 116754637679537 79587668206509 80161279644028

Sample Output #2

705437004

Notes

\(SA, SB, SC\) are all within the range of the unsigned long long data type, which means the returned \(n\) values are also within the range of the unsigned long long data type.

The first 6 test points each worth 1 point.

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 \times 10^7\).

见题面 Input 部分

见题面 Output 部分