Problem Description

有一个大小为 $n$ 的数组 $a_1,...,a_{n}$。

$a[l, r]$ 表示可重集合 $\{a_l \ldots a_r\}$。

有 $q$ 次询问，输出 $a[l, r]$ 有多少子集的和是 $k$ 的倍数。

答案对 $998244353$ 取模。

Input

第一行给出 $n, k$。

第二行给出 $n$ 个数字 $a_1,\ldots a_n$。

接下来给一个 $q$。

然后 $q$ 行，每行一个 $l, r$ 表示一次询问。


#### 评测数据规模

$n, q \leq 2 \times 10^5, 0 \leq a_i < k \leq 100$.

并且保证每次询问 $l \leq r$.

Output

输出一行，表示 $q$ 次询问的答案。

特别的，注意空集也是一种答案。

#### 样例解释

$[3, 4]$ 的答案有 $\empty, \{a_4\}$.

$[2, 4]$ 的答案有 $\empty,\{a_2,a_3\},\{a_4\},\{a_2,a_3,a_4\}$.

$[4, 4]$ 的答案有 $\empty,\{a_4\}$.

4 2
0 1 1 0
3
3 4
2 4
4 4

2 4 2