给定一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$ 与一个参数 $k$。

现有 $q$ 次询问，每次询问一个区间 $[L,R]$，请你求出该区间内所有子集和中，有多少个子集和恰好是 $k$ 的倍数，答案对 $998244353$。（注意：所有子集中包含空集）

数据范围：

• $1 \leqslant n, q \leqslant 10^5$
• $1 \leqslant k \leqslant 20$
• $1 \leqslant a_i \leqslant 10^9$