D - A xor B plus C Editorial /

Time Limit: 8 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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:

  • X_1 = A
  • X_2 = B
  • X_{i+2} = (X_i \oplus X_{i+1}) + C\ \ (i=1,2,\dots)

Here, \oplus represents the bitwise XOR operation.

You are also given a positive integer N. Calculate X_N \bmod 998244353.

Constraints

  • All input values are integers.
  • 0 \leq A, B, C < 2^{20}
  • 1 \leq N \leq 10^{18}

Input

The input is given from Standard Input in the following format:

A B C N

Output

Output X_N \bmod 998244353.

Sample Input 1

1 2 3 4

Sample Output 1

7

X = (1, 2, 6, 7, \dots). Here, X_4 = 7 is the answer.

Sample Input 2

123 456 789 123456789

Sample Output 2

567982455

Sample Input 3

0 0 0 1000000000000000000

Sample Output 3

0

配点 : 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 はビットごとの排他的論理和 (bitwise XOR) を表します。

正整数 N が与えられます。 X_N\bmod 998244353 を求めてください。

制約

  • 入力はすべて整数
  • 0\le A,B,C\lt 2^{20}
  • 1\le N\le 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