U574181 子集和（六）

给定一个长度为$\ n\ $的序列$\ a_1,a_2,...,a_n\ $与一个参数$\ k\ $。 现有$\ q\ $次询问，每次询问一个区间$\ [L,R]$，请你求出该区间内所有子集和中，有多少个子集和恰好是$\ k\ $的倍数，答案对$998244353$取模。（注意：所有子集中包含空集）

* 输入第一行，三个正整数$\ n,q,k$ * 输入第二行，$n\ $个正整数$\ a_1,a_2,...,a_n$ * 接下来$\ q\ $行， 每行两个正整数，表示询问区间的左右端点$L_i,R_i$

输出共$\ q\ $行，第$\ i\ $行的整数表示第$\ i\ $个询问的答案

#### 数据范围 * 对于$30\%$的数据，$1\leq n,q \leq 10$ * 对于$60\%$的数据，$1\leq n,q \leq 10^3$ * 对于$100\%$的数据，$1\leq n,q \leq 10^5\ $,$\ 1 \leq k \leq 20$，$\ 1 \leq a_i \leq 10^9$