{"raw_statement":[{"iden":"problem statement","content":"You are given non-negative integers $A$, $B$, and $C$. Define a sequence of non-negative integers $X = (X_1, X_2, \\dots)$ as follows:\n\n*   $X_1 = A$\n*   $X_2 = B$\n*   $X_{i+2} = (X_i \\oplus X_{i+1}) + C\\ \\ (i=1,2,\\dots)$\n\nHere, $\\oplus$ represents the bitwise XOR operation.\nYou are also given a positive integer $N$. Calculate $X_N \\bmod 998244353$."},{"iden":"constraints","content":"*   All input values are integers.\n*   $0 \\leq A, B, C < 2^{20}$\n*   $1 \\leq N \\leq 10^{18}$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$A$ $B$ $C$ $N$"},{"iden":"sample input 1","content":"1 2 3 4"},{"iden":"sample output 1","content":"7\n\n$X = (1, 2, 6, 7, \\dots)$. Here, $X_4 = 7$ is the answer."},{"iden":"sample input 2","content":"123 456 789 123456789"},{"iden":"sample output 2","content":"567982455"},{"iden":"sample input 3","content":"0 0 0 1000000000000000000"},{"iden":"sample output 3","content":"0"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}