405020: GYM101741 J 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_j1, a_j2, ..., a_jk that l_i ≤ j₁ < j₂ < ... < j_k ≤ r_i and . In other words, you need to calculate the number of subsequences of subarray [a_li, a_li + 1, ..., a_ri] 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 ≤ n ≤ 2·10⁵, 1 ≤ m ≤ 20).

The second line contains n integers a_i: the elements of array a (0 ≤ a_i ≤ 10⁹).

The third line contains one integer q: the number of queries (1 ≤ q ≤ 2·10⁵).

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 ≤ l_i ≤ r_i ≤ 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⁹ + 7.

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

2
4
6
4