Recurrence XOR Challenge

Given a sequence (a_n) defined for (n \in {0,1,2,\cdots,2^{64}-1}) with initial values

[ a_0 = -3,\quad a_1 = -6,\quad a_2 = -12, ]

and recurrence

[ a_n = 3a_{n-1} + a_{n-2} - 3a_{n-3} + 3^n, ]

for (n \ge 3). Given a non-negative integer (n) and (p = 10^9+7), your task is to compute (a_n \bmod p). If (a_n < 0), output (((a_n \bmod p) + p) \bmod p).

There are (T) queries. However, to reduce I/O, the queries are generated via a pseudo-random process. After reading two numbers (sd) and (op), the generator works as follows:

[ \begin{aligned} \text{ull_rand}() &:; sd \mathrel{\oplus}= sd \ll 43,\ &; sd \mathrel{\oplus}= sd \gg 29,\ &; sd \mathrel{\oplus}= sd \ll 34,\ \text{rand}() &:; = \begin{cases}\text{ull_rand()} \bmod 65535 + 1, & \text{if } op = 0,\[5mm] &\quad \text{ull_rand()} \bmod 4294967295 + 1, & \text{if } op = 1,\[5mm] &\quad \text{ull_rand()}, & \text{if } op = 2.\end{cases} \end{aligned} ]

After initialization (i.e. after calling the provided (Mker::init()) procedure), the (i)-th call to (Mker::rand()) returns the query (n_i). You must answer all queries and finally output the bitwise XOR of all (a_{n_i} \bmod p).

A closed‐form expression for (a_n) can be derived and is given by

[ a_n = \frac{9}{8} + 3^n\cdot\frac{36n - 117}{32} - \frac{15}{32}\cdot(-1)^n. ]

Be sure to take all operations modulo (p) and handle negative values as described.

inputFormat

The input begins with two space‐separated integers sd and op on the first line. The second line contains a positive integer T – the number of queries. The queries themselves are generated by the pseudo-random generator described above.

outputFormat

Output a single integer: the bitwise XOR of all answers \(a_{n_i} \bmod p\) for \(i = 1,2,\ldots,T\).

sample

0 0
3

1000000001