Exponential Recurrence and XOR Queries

Given a sequence \(a\) defined by the recurrence \[ a_{n} = 233\,a_{n-1} + 666\,a_{n-2}, \quad a_{0} = 0, \quad a_{1} = 1, \] compute \(a_{n}\) modulo \(10^9+7\). There are \(T\) queries. However, instead of reading each query \(n\) directly, you must generate it using the following pseudorandom number generator:

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

After calling Mker::init() to initialize the generator with three unsigned 64-bit integers, the \(i\)-th call to Mker::rand() yields the \(i\)-th query value \(n\). For each query you must compute \(a_{n}\) modulo \(10^9+7\), and finally output the XOR (bitwise exclusive or) of all these answers.

inputFormat

The input consists of a single test case. The first line contains an integer \(T\) representing the number of queries. The next line contains three unsigned 64-bit integers \(SA\), \(SB\), and \(SC\), which are the seeds for the pseudorandom generator. To obtain the \(i\)-th query, call the function Mker::rand(); its return value is \(n\) for that query.

outputFormat

Output a single integer: the XOR of the answers to all queries. For a query with value \(n\), the answer is \(a_{n} \bmod (10^9+7)\), where \(a_{n}\) is the \(n\)-th term of the sequence defined above.

sample

3
0 0 0

0