如果一个正整数的多重集中的所有元素都是 2 的幂，则称该多重集为“好集”。 对于非负整数 $N$，定义 $f(N)$ 为：

$$f(N) = \sum_{T \in S_N} \prod_{i \in T} i$$

其中 $S_N$ 是所有元素之和为 $N$ 的好集构成的集合。注意，空集的元素之和定义为 0，空集的元素之积定义为 1。因此，我们定义 $f(0) = 1$。 给定三个非负整数 $T, a$ 和 $b$。 定义 $N_i$ 为 $N_i = (ai + b) \pmod{2^{30}}$。计算以下值：

$$\sum_{i=0}^{T-1} (f(N_i) \pmod{998244353}) \oplus i$$

其中 $\oplus$ 表示按位异或运算。

输入格式

输入通过标准输入按以下格式给出：

$T \ a \ b$

• $1 \le T \le 10^7$
• $0 \le a, b < 2^{30}$
• 所有输入值均为整数。

输出格式

在一行中输出答案。

样例

样例输入 1

5 1 0

样例输出 1

17

样例输入 2

3 1000000000 1000000000

样例输出 2

1217611736

说明

在第一个样例中，$N_0 = 0, N_1 = 1, N_2 = 2, N_3 = 3$ 且 $N_4 = 4$。

• 和为 0 的好集为 $\{\}$。因此，$f(0) = 1$。
• 和为 1 的好集为 $\{1\}$。因此，$f(1) = 1$。
• 和为 2 的好集为 $\{1, 1\}$ 和 $\{2\}$。因此，$f(2) = (1 \times 1) + (2) = 3$。
• 和为 3 的好集为 $\{1, 1, 1\}$ 和 $\{1, 2\}$。因此，$f(3) = (1 \times 1 \times 1) + (1 \times 2) = 3$。
• 和为 4 的好集为 $\{1, 1, 1, 1\}, \{1, 1, 2\}, \{2, 2\}$ 和 $\{4\}$。 因此，$f(4) = (1 \times 1 \times 1 \times 1) + (1 \times 1 \times 2) + (2 \times 2) + (4) = 11$。

因此，答案为 $(1 \oplus 0) + (1 \oplus 1) + (3 \oplus 2) + (3 \oplus 3) + (11 \oplus 4) = 17$。

在第二个样例中，$N_0 = 1000000000, N_1 = 926258176$ 且 $N_2 = 852516352$。