分数: 100 点
问题陈述
给你非负整数 A, B,和 C。定义一个非负整数序列 X = (X_1, X_2, \dots) 如下:
- X_1 = A
- X_2 = B
- X_{i+2} = (X_i \oplus X_{i+1}) + C\ \ (i=1,2,\dots)
在这里, \oplus 表示按位异或(XOR)运算。
还给你一个正整数 N。计算 X_N \bmod 998244353.
约束
- 所有输入值均为整数。
- 0 \leq A, B, C < 2^{20}
- 1 \leq N \leq 10^{18}
输入
输入由标准输入按以下格式给出:
A B C N
输出
输出 X_N \bmod 998244353.
示例输入 1
1 2 3 4
示例输出 1
7
X = (1, 2, 6, 7, \dots)。在这里, X_4 = 7 就是答案。
示例输入 2
123 456 789 123456789
示例输出 2
567982455
示例输入 3
0 0 0 1000000000000000000
示例输出 3
0