AT_ttpc2024_1_d A xor B plus C

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 $ .

The input is given from Standard Input in the following format: > $ A $ $ B $ $ C $ $ N $

Output $ X_N \bmod 998244353 $ .

### Sample Explanation 1 $ X = (1, 2, 6, 7, \dots) $ . Here, $ X_4 = 7 $ is the answer. ### Constraints - All input values are integers. - $ 0 \leq A, B, C < 2^{20} $ - $ 1 \leq N \leq 10^{18} $