부분 수열 합 쿼리

정수 $n$개로 이루어진 배열 $a$와 정수 $m$이 주어진다. 질의 $q$개에 답해야 한다. $i$번째 질의는 정수 쌍 $(l_i, r_i)$로 주어진다. 각 질의마다 $l_i \le j_1 < j_2 < \cdots < j_k \le r_i$를 만족하고, 합 $a_{j_1} + a_{j_2} + \cdots + a_{j_k}$가 $m$으로 나누어떨어지는 부분 수열 $a_{j_1}, a_{j_2}, \ldots, a_{j_k}$의 개수를 구한다. 달리 말하면, 부분 배열 $[a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}]$의 부분 수열 중 원소의 합이 $m$의 배수인 것의 개수를 구한다.

첫 줄에 정수 $n$과 $m$이 주어진다 ($1 \le n \le 2 \times 10^5$, $1 \le m \le 20$).

둘째 줄에 정수 $a_i$가 $n$개 주어진다 ($0 \le a_i \le 10^9$).

셋째 줄에 질의의 개수 $q$가 주어진다 ($1 \le q \le 2 \times 10^5$).

이어서 $q$개의 줄에 각각 정수 $l_i$와 $r_i$가 주어진다 ($1 \le l_i \le r_i \le n$).

$q$개의 줄을 출력한다. $i$번째 줄에는 $i$번째 질의의 답을 입력과 같은 순서로 출력한다. 답은 $10^9+7$로 나눈 나머지를 출력한다.