Sequence Query
Limits
2.5s, 512 MB
You are given N integer numbers (A1,A2,A3…AN). You will also be given some query. Each query will be of the format (L,R). For each query you need to find all the sequence such that
L≤v1<v2<v3…<vk≤R, and (Av1+Av2+Av3+…+Avk) is divisible by M. You need to find out the sum of product of all the numbers in all such sequences. Basically SUM of all possible(Av1∗Av2∗Av3∗…∗Avk).
Input
The first line contains three integers N, Q, M (1≤N,Q≤300000,1≤M≤30). The following line contains N integers A1, A2, A3, …, AN (0≤Ai<1000000000). The next Q lines each contain two integers L, R (1≤L≤R≤N).
Output
Print Q lines, each line must contain the result of the query modulo 1000000007
Sample
Input | Output |
---|
5 2 2
1 2 3 4 5
1 5
2 4
| 359
14
|