给定非负整数 $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 \quad (i = 1, 2, \dots)$

其中，$\oplus$ 表示按位异或运算。 给定一个正整数 $N$，计算 $X_N \pmod{998244353}$。

输入格式

$A \ B \ C \ N$

• 所有输入值均为整数。
• $0 \le A, B, C < 2^{20}$
• $1 \le N \le 10^{18}$

输出格式

输出 $X_N \pmod{998244353}$。

样例

样例输入 1

1 2 3 4

样例输出 1

7

样例输入 2

123 456 789 123456789

样例输出 2

567982455

样例输入 3

0 0 0 1000000000000000000

样例输出 3

0

说明

在第一个样例中，$X = (1, 2, 6, 7, \dots)$。此处 $X_4 = 7$ 为答案。