时空限制

2S/512M

题目描述

有 $R$ 个红砖块和 $B$ 个蓝砖块。你需要将这 $R+B$ 个砖块排成一排。一个合法的排列需要满足以下两个条件：

1. 颜色交替: 排列中，相邻砖块颜色不同的位置恰好有 $K$ 个。这等价于，整个砖块序列恰好由 $K+1$ 个颜色连续的 “块” 组成。例如 RR B RRR 由 $3$ 个块组成，其颜色交替位置有 $2$ 个。
2. 长度限制: 任意一个颜色连续的块，其长度（包含的砖块数）都不能超过 $L$。

你的任务是：对于每一个可能的长度限制 $i$（$i$ 从 $1$ 到 $M$，其中 $M = \max(R, B)$），计算满足上述条件的排列方案数，记为 $ans_i$。由于方案数可能很大，每个 $ans_i$ 都需要对 $998244353$ 取模。

为了减少输出量，你需要计算所有 $i \times ans_i$ 的异或和，即 $(1 \times ans_1) \oplus (2 \times ans_2) \oplus \dots \oplus (\max(R,B) \times ans_{\max(R,B)})$，作为最终的答案。其中 $\oplus$ 表示按位异或运算。（ $i \times ans_{i}$ 不需要对 $998244353$ 取模。）

格式

输入格式

输入仅一行，包含三个整数 $R, B, K$。

输出格式

输出一个整数，表示根据题目描述中定义的计算方式得到的最终异或和。

样例

样例输入 #1

3 2 3

样例输出 #1

4

样例输入 #2

10000 92312 334

样例输出 #2

35448238732126

数据规模

对于 $30\%$ 的测试数据，$0\leq R,B \leq 300$。

对于 $60\%$ 的测试数据，$0 \leq R,B \leq 2000$。

对于 $100\%$ 的测试数据，$0 \le R, B \le 10^6$，$0 \le K < R+B$，且 $R,B$ 不同时为 $0$。