题目描述

给定一个长度为 $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$ 个询问的答案

10 3 7
3 5 8 1 4 9 8 2 7 6
1 9
2 5
4 8

72
2
5

数据范围

• 对于$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$