시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 256 MB 2 2 2 100.000%


You have an array $a$ containing $n$ integers and an integer $m$. You also have $q$ queries to answer. The $i$-th query is described as a pair of integers $(l_i, r_i)$. Your task is to calculate the number of such subsequences $a_{j_1}, a_{j_2}, \ldots, a_{j_k}$ that $l_i \le j_1 < j_2 < \ldots < j_k \le r_i$ and $(a_{j_1} + a_{j_2} + \ldots + a_{j_k}) \bmod m = 0$. In other words, you need to calculate the number of subsequences of subarray $[a_{l_i}, a_{l_i + 1}, \ldots, a_{r_i}]$ such that the sum of elements in each subsequence is divisible by $m$.


The first line contains two integers $n$ and $m$: the number of elements in $a$ and the modulo ($1 \le n \le 2 \cdot 10^5$, $1 \le m \le 20$).

The second line contains $n$ integers $a_i$: the elements of array $a$ ($0 \le a_i \le 10^9$).

The third line contains one integer $q$: the number of queries ($1 \le q \le 2 \cdot 10^5$).

Then $q$ lines follow. The $i$-th of these lines contains two integers $l_i$ and $r_i$ that describe the $i$-th query ($1 \le l_i \le r_i \le n$).


Print $q$ lines. The $i$-th of them must contain the answer for the $i$-th query. Queries are indexed in the order they are given in the input. Since the answers can be very large, print them modulo $10^9 + 7$.

예제 입력 1

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

예제 출력 1