\(Alice\) loves number \(k\) and base-\(k\)! She wants to give \(Bob\) an exam about base-\(k\).
\(Alice\) gives \(Bob\) two sequences \(\{a\}=\{a_0,\ldots,a_{k-1}\}\) and \(\{b\}=\{b_0,\ldots,b_{k-1}\}\). Obviously, each of them has excatly \(k\) numbers.
Define function\(\space A(x),B(x),G(x,y),\mathrm{operation} \oplus(xor),\space \mathrm{operation} \space \wedge(and)\) as follows:
\(A(x)= \prod_{i=0} a[x_{i}],B(x)=\prod_{i=0}b[x_i]\)
\(z=x\oplus y\ :\ z_i=(x_i+y_i) mod\ k\)
\(z=x \wedge y\ :\ z_i=min\{x_i,y_i\}\)
\(G(x,y)=A(x\oplus y)\times B(x \wedge y)\)
Now \(Alice\) tells \(Bob\) the number \(k\) and other three numbers \(s,t,n\).
\(Bob\)'s task is to calculate {\(\sum_{i=0}^{n} G(i \times s, i \times t)\ mod\ (998244353)\)}.
For example, in Case1, \(k=2,\{a\}=\{1,3\}\).
we let \(x=11\), so \(x\) is \(1011_{(2)},x_0=1,x_1=1,x_2=0,x_3=1\).
\(A(x)=3 \times 3 \times 1 \times 3=27,B(x)=5 \times 5 \times 1 \times 5=125\).
and we let \(y=13=1101_{(2)}\), so \(x \oplus y=110_{2}=6,x \wedge y=1001_{2}=9\).
Obviously, \(A(1)=3,B(2)=5,G(2,3)=A(2 \oplus 3) \times B(2 \wedge 3)=15\).