問題文

正整数の多重集合が 良い集合 であるとは、含まれる要素がすべて 2 べきであることをいいます。

非負整数 N に対して、要素の総和が N であるような良い集合それぞれについて要素の総積を計算したとき、それらの総和を f(N) とします。ただし、空集合の要素の総和は 0、総積は 1 として f(0)=1 とします。

非負整数 T,a,b が与えられます。 N_i=(ai+b)\ \mathrm{mod}\ 2^{30} としたとき、 \displaystyle \sum_{i=0}^{T-1}(f(N_i)\ \mathrm{mod}\ 998244353)\oplus i を求めてください。 ここで、 \oplus はビットごとの排他的論理和です。

制約

• 1\leq T\leq 10^7
• 0\leq a,b\lt 2^{30}
• 入力は全て整数

部分点

この問題には複数の部分点が設定されている。

• 追加の制約 T\leq 10^6,a=1,b=0 を満たすデータセットに正解した場合は 10 点が与えられる。
• 追加の制約 T\leq 1000 を満たすデータセットに正解した場合は 10 点が与えられる。

入力例 1

5 1 0

出力例 1

17

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

• 総和が 0 である良い集合は \lbrace\rbrace であり、 f(0)=1 です。
• 総和が 1 である良い集合は \lbrace1\rbrace であり、 f(1)=1 です。
• 総和が 2 である良い集合は \lbrace1,1\rbrace,\lbrace2\rbrace であり、 f(2)=(1\times 1)+(2)=3 です。
• 総和が 3 である良い集合は \lbrace1,1,1\rbrace,\lbrace1,2\rbrace であり、 f(3)=(1\times 1\times 1)+(1\times 2)=3 です。
• 総和が 4 である良い集合は \lbrace1,1,1,1\rbrace,\lbrace1,1,2\rbrace,\lbrace2,2\rbrace,\lbrace4\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

3 1000000000 1000000000

出力例 2

1217611736

N_0=1000000000,N_1=926258176,N_2=852516352 です。