AT_ttpc2024_1_d A xor B plus C

非負整数 $ 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 $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ A $ $ B $ $ C $ $ N $

$ X_N \bmod 998244353 $ を出力せよ。

### Sample Explanation 1 $ X=(1,2,6,7,\dots) $ です。 $ X_4=7 $ が答えとなります。 ### Constraints - 入力はすべて整数 - $ 0\le A,B,C\lt 2^{20} $ - $ 1\le N\le 10^{18} $