19333번 - Subsequence Sum Queries 다국어

문제

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$.

제한

힌트