#P18238. A xor B plus C

A xor B plus C

A xor B plus C

题目描述

给定非负整数 A,B,CA,B,C,定义非负整数序列 X=(X1,X2,…)X=(X_1,X_2,\ldots):

X1=A,X2=B,X_1=A,\qquad X_2=B, $$X_{i+2}=(X_i\oplus X_{i+1})+C\qquad(i=1,2,\ldots).$$

其中,⊕\oplus 表示按位异或。

再给定一个正整数 NN,求 XN mod 998244353X_N\bmod998244353。

输入格式

一行四个整数 A,B,C,NA,B,C,N。

输出格式

输出一个整数,表示 XN mod 998244353X_N\bmod998244353。

数据范围

所有输入均为整数。

  • 0≤A,B,C<2200\le A,B,C<2^{20}。
  • 1≤N≤10181\le N\le10^{18}。

样例 1

1 2 3 4
7

样例 1 说明

X=(1,2,6,7,…)X=(1,2,6,7,\ldots),所以 X4=7X_4=7。

样例 2

123 456 789 123456789
567982455

样例 3

0 0 0 1000000000000000000
0

来源

The 3rd Universal Cup Stage 21: Ōokayama,Problem D,原题为 Tokyo Tech Programming Contest 2024 Div.1 D。