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)

This is a companion discussion topic for the original entry at