Groudon wanna fly. Kyogre will tell Groudon how to fly if and only if Groudon solves the following problem.
There are nnn integers a1,a2,…,ana_1,a_2,\ldots,a_na1,a2,…,an, one integer mmm and kkk integer pairs (b1,c1),(b2,c2),…,(bk,ck)(b_1,c_1), (b_2,c_2), \ldots, (b_k,c_k)(b1,c1),(b2,c2),…,(bk,ck). You need to find the number of non-negative nnn-tuples (x1,x2,…,xn)(x_1,x_2,\ldots,x_n)(x1,x2,…,xn) which satisfies:
{∑i=1naixi≤mxbi&2ci=0 for i=1,2,…,k\begin{cases}
\displaystyle \sum_{i=1}^na_ix_i \le m \\
\displaystyle x_{b_i} \operatorname{\&} 2^{c_i} = 0 \text{ for } i =1,2,\ldots,k
\end{cases}⎩⎪⎨⎪⎧i=1∑naixi≤mxbi&2ci=0 for i=1,2,…,k
Here, &\operatorname{\&}& denotes the bitwise operation AND.
Two non-negative nnn-tuples (x1,x2,…,xn)(x_1,x_2,\ldots,x_n)(x1,x2,…,xn) and (x1′,x2′,…,xn′)(x'_1,x'_2,\ldots,x'_n)(x1′,x2′,…,xn′) are considered different if and only if there exists one integer i∈[1,n]i \in [1,n]i∈[1,n] which satisfies xi≠xi′x_i \ne x'_ixi=xi′.
Since the answer is too large, Kyogre only wants to know it modulo 998244353998\,244\,353998244353.
You, as a programmer of Hoenn, please help Groudon!