← 返回题目列表

AtCoder · ttpc2024_1_d

D. A 异或 B 加 C

中文机器翻译题面 查看原题

分数: 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 表示按位异或(XOR)运算。

还给你一个正整数 N。计算 X_N \bmod 998244353.

约束

  • 所有输入值均为整数。
  • 0 \leq A, B, C < 2^{20}
  • 1 \leq N \leq 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