给定一个包含 $n$ 个整数的数组 $a$ 和一个整数 $m$。你需要回答 $q$ 个询问。第 $i$ 个询问由一对整数 $(l_i, r_i)$ 描述。你的任务是计算满足 $l_i \le j_1 < j_2 < \dots < j_k \le r_i$ 且 $(a_{j_1} + a_{j_2} + \dots + a_{j_k}) \pmod m = 0$ 的子序列 $a_{j_1}, a_{j_2}, \dots, a_{j_k}$ 的数量。换句话说，你需要计算子数组 $[a_{l_i}, a_{l_i+1}, \dots, a_{r_i}]$ 中所有元素之和能被 $m$ 整除的子序列的数量。

输入格式

第一行包含两个整数 $n$ 和 $m$：数组 $a$ 的元素个数和模数 ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 20$)。

第二行包含 $n$ 个整数 $a_i$：数组 $a$ 的元素 ($0 \le a_i \le 10^9$)。

第三行包含一个整数 $q$：询问次数 ($1 \le q \le 2 \cdot 10^5$)。

接下来 $q$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$，描述第 $i$ 个询问 ($1 \le l_i \le r_i \le n$)。

输出格式

输出 $q$ 行。第 $i$ 行必须包含第 $i$ 个询问的答案。询问按输入给出的顺序编号。由于答案可能非常大，请将其对 $10^9 + 7$ 取模后输出。

样例

样例输入 1

4 3
5 1 3 2
4
1 2
1 3
1 4
2 4

样例输出 1

2
4
6
4