Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Sequence Query

Limits: 2.5s, 256 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 thatL <= 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

Samples

InputOutput
5 2 2
1 2 3 4 5
1 5
2 4
359
14

Author
  • nfssdq's Avatar

    nfssdq

    Nafis was a student of Jahangirnagar University, a die-hard programming contestant. His team became the champion in ACM-ICPC Dhaka Regional 2015. He participated in the 39th and 40th ACM-ICPC World Finals.
Discussion