称正整数的多重集合为好集合，当且仅当其中所有元素都是 $2$ 的幂。

对于一个非负整数 $N$，定义 $f(N)$ 为所有元素之和为 $N$ 的好集合的元素之积的总和。特别地，空集的元素和为 $0$，元素积为 $1$，因此 $f(0)=1$。

给定非负整数 $T, a, b$。令 $N_i=(a i + b)\ \mathrm{mod}\ 2^{30}$，请计算 $\displaystyle \sum_{i=0}^{T-1}(f(N_i)\ \mathrm{mod}\ 998244353)\oplus i$。其中，$\oplus$ 表示按位异或（XOR）。

按位异或是这样定义的：对于非负整数 $A,B$，$A \oplus B$ 的第 $2^k$ 位（二进制下，第 $k$ 位），仅当 $A,B$ 在该位有且仅有一个为 $1$ 时，该位为 $1$，否则为 $0$。

例如，$3\oplus 5 = 6$，因为二进制表示时 $011 \oplus 101 = 110$。

输入为一行，包含三个整数：

$T\ a\ b$

输出计算结果。

部分分

本题包含若干部分分。

• 满足 $T\leq 10^6,\ a=1,\ b=0$ 的数据集，得分为 $10$ 分。
• 满足 $T\leq 1000$ 的数据集，得分为 $10$ 分。

样例解释 1

$N_0=0,N_1=1,N_2=2,N_3=3,N_4=4$。

• 和为 $0$ 的好集合只有 $\lbrace\rbrace$，$f(0)=1$。
• 和为 $1$ 的好集合只有 $\lbrace 1\rbrace$，$f(1)=1$。
• 和为 $2$ 的好集合有 $\lbrace 1, 1\rbrace$、$\lbrace 2\rbrace$，$f(2)=(1\times 1)+(2)=3$。
• 和为 $3$ 的好集合有 $\lbrace 1,1,1\rbrace$、$\lbrace 1,2\rbrace$，$f(3)=(1\times 1\times 1)+(1\times 2)=3$。
• 和为 $4$ 的好集合有 $\lbrace 1,1,1,1\rbrace$、$\lbrace 1,1,2\rbrace$、$\lbrace 2,2\rbrace$、$\lbrace 4\rbrace$，$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$。

样例解释 2

$N_0=1000000000,N_1=926258176,N_2=852516352$。

数据范围

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

由 ChatGPT 5 翻译