For a series FFF:

F(0)=0,F(1)=1F(n)=3∗F(n−1)+2∗F(n−2),(n≥2)\displaystyle \begin{gathered} F(0) = 0,F(1) = 1\\ F(n) = 3*F(n-1)+2*F(n-2),(n \geq 2) \end{gathered} F(0)=0,F(1)=1F(n)=3∗F(n−1)+2∗F(n−2),(n≥2)​

 

We have some queries. For each query NNN, the answer AAA is the value F(N)F(N)F(N) modulo 998244353998244353998244353.

Moreover, the input data is given in the form of encryption, only the number of queries QQQ and the first query N1N_1N1​ are given. For the others, the query Ni(2≤i≤Q)N_i(2\leq i\leq Q)Ni​(2≤i≤Q) is defined as the xor of the previous Ni−1N_{i-1}Ni−1​ and the square of the previous answer Ai−1A_{i-1}Ai−1​. For example, if the first query N1N_1N1​ is 222, the answer A1A_1A1​ is 333, then the second query N2N_2N2​ is 2 xor (3∗3)=112 \ xor \ ( 3*3)=112 xor (3∗3)=11.

Finally, you don't need to output all the answers for every query, you just need to output the xor of each query's answer A1 xor A2...xor AQA_1\ xor\ A_2 ... xor\ A_QA1​ xor A2​...xor AQ​.

Input

The input contains two integers, Q,NQ, NQ,N, 1 ≤ Q≤107,0 ≤ N≤10181\ \leq \ Q \leq 10^7,0\ \leq\ N \leq 10^{18}1 ≤ Q≤107,0 ≤ N≤1018. QQQ representing the number of queries and NNN representing the first query.

Output:

An integer representing the final answer.

样例输入

17 473844410

样例输出

903193081

题意：给你一个递推式，q次询问，每次询问的n由上一次答案异或得到

思路：一开始就觉得矩阵快速幂会超时，没想到map记忆化一下就能过了。。。

#include <cstdio>
#include<iostream>
#include<cstring>
#include<map>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
map<ll,ll>mp;
inline ll read(){
    ll x = 0;char c = 0;
    c = getchar();
    while(isdigit(c)) x = (x<<1)+(x<<3)+(c^48),c = getchar();
    return x;
}
struct matrix{
    ll x[2][2];
};
matrix muli(matrix a,matrix b){
    matrix temp;
    memset(temp.x,0,sizeof(temp.x));
    for(register int i = 0; i < 2; i++)
    for(register int j = 0; j < 2; j++)
    for(register int k = 0; k < 2; k++){
        temp.x[i][j]+=a.x[i][k]*b.x[k][j];
        temp.x[i][j]%=mod;
    }
    return temp;
}
matrix pows(matrix a,ll b){
    matrix e;
    memset(e.x,0,sizeof(e));
    for(register int i = 0; i < 2; i++) e.x[i][i] = 1;
    matrix ans = e;
    while(b){
        if(b&1) ans=muli(ans,a);
            a=muli(a,a);
        b>>=1;
    }
    return ans;
}
int main() {
    ll n,q;
    q = read(),n = read();
    matrix a;
    a.x[0][0] = 3;a.x[0][1] = 1;a.x[1][0] = 1;a.x[1][1] = 0;
    matrix b;
    b.x[0][0] = 3;b.x[0][1] = 1;b.x[1][0] = 2;b.x[1][1] = 0;
    ll ans = 0;
    matrix a1,b1;
    mp[0] = 0;mp[1] = 1;
    for(register ll i = 1; i <= q; i++){
        if(mp.count(n)==0){
            b1=pows(b,n-2);
            a1=muli(a,b1);
            ans=ans^a1.x[0][0];
            mp[n] = a1.x[0][0];
            n=n^(a1.x[0][0]*a1.x[0][0]);
        }else{
            ans^=mp[n];
            n^=(mp[n]*mp[n]);
        }
    }
    printf("%lld\n",ans);
    return 0;
}