Subsequence Sum Queries

You are given an array $a$ of $n$ integers and an integer $m$. You must answer $q$ queries. The $i$-th query is a pair of integers $(l_i, r_i)$. For each query, count the subsequences $a_{j_1}, a_{j_2}, \ldots, a_{j_k}$ with $l_i \le j_1 < j_2 < \cdots < j_k \le r_i$ whose sum $a_{j_1} + a_{j_2} + \cdots + a_{j_k}$ is divisible by $m$. In other words, count the subsequences of the subarray $[a_{l_i}, a_{l_i+1}, \ldots, a_{r_i}]$ whose element sum is a multiple of $m$.

The first line contains two integers $n$ and $m$ ($1 \le n \le 2 \times 10^5$, $1 \le m \le 20$).

The second line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$).

The third line contains one integer $q$ ($1 \le q \le 2 \times 10^5$).

Each of the next $q$ lines contains two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

Print $q$ lines. The $i$-th line must contain the answer to the $i$-th query, in the order the queries are given. Print each answer modulo $10^9+7$.