#P18324. 2-Power Rush

2-Power Rush

2-Power Rush

如果一个正整数多重集的每个元素都是 22 的非负整数次幂,就称它为好集合。多重集允许相同元素重复出现,元素的排列顺序不区分集合。

对非负整数 NN,记 SNS_N 为所有元素之和等于 NN 的好集合构成的集合。定义

f(N)=∑X∈SN ∏x∈Xx.f(N)=\sum_{X\in S_N}\ \prod_{x\in X}x.

约定空多重集的元素和为 00,元素乘积为 11,因此 f(0)=1f(0)=1。

给定整数 T,a,bT,a,b。对 i=0,1,…,T−1i=0,1,\ldots,T-1,定义

Ni=(ai+b) mod 230.N_i=(ai+b)\bmod 2^{30}.

请计算

$$\sum_{i=0}^{T-1}\left(\bigl(f(N_i)\bmod998244353\bigr)\mathbin{\oplus}i\right),$$

其中 ⊕\oplus 表示按位异或。每一项先对 f(Ni)f(N_i) 取模,再与 ii 异或;最终总和不再取模。

输入格式

一行三个整数 T,a,bT,a,b。

输出格式

输出一行一个整数,表示要求的总和。

数据范围

  • 1≤T≤1071\le T\le10^7;
  • 0≤a,b<2300\le a,b<2^{30};
  • 所有输入值均为整数。

样例 1

样例输入 1

5 1 0

样例输出 1

17

样例 2

样例输入 2

3 1000000000 1000000000

样例输出 2

1217611736

样例说明

第一个样例中,N0,…,N4N_0,\ldots,N_4 依次为 0,1,2,3,40,1,2,3,4。

  • 和为 00 的好集合只有空集,因此 f(0)=1f(0)=1。
  • 和为 11 的好集合只有 {1}\{1\},因此 f(1)=1f(1)=1。
  • 和为 22 的好集合为 {1,1},{2}\{1,1\},\{2\},因此 f(2)=1+2=3f(2)=1+2=3。
  • 和为 33 的好集合为 {1,1,1},{1,2}\{1,1,1\},\{1,2\},因此 f(3)=1+2=3f(3)=1+2=3。
  • 和为 44 的好集合为 {1,1,1,1},{1,1,2},{2,2},{4}\{1,1,1,1\},\{1,1,2\},\{2,2\},\{4\},因此 f(4)=1+2+4+4=11f(4)=1+2+4+4=11。

答案为 $(1\oplus0)+(1\oplus1)+(3\oplus2)+(3\oplus3)+(11\oplus4)=17$。

第二个样例中,N0,N1,N2N_0,N_1,N_2 分别为 1000000000,926258176,8525163521000000000,926258176,852516352。