Happy and sum

5

1 votes
Combinatorics, Dynamic Programming, Algorithms, Approved, Medium-Hard
Problem

Once, happy and his friends were playing with a list of numbers. They take a subset of the numbers from the given list and add the numbers in the subset. As this was a very simpler task and happy loves counting, he decided to find the number of subsets from the given list that form a particular sum. Seeing this, his friend asks him to tell the number of subsets whose sum of elements lies in a given range. As this value can be very large, he asks happy to tell the answer modulo 109 + 7.

The list consists of N integers and his friend asks him M queries. In each query, he will give two numbers L and R to happy and he has to tell the number of subsets that has the sum of its elements in the range L to R ( both inclusive).

The subsets S1 and S2 are considered different if there exist at least one index i that belongs to S1 but does not belong to S2 where i [1, N].

Input:

The first line of the input consists of integers N and M.

The second line of the input contains N single space separated integers.
The next M lines of input consists of the integers L and R for which happy has to tell the answer.

Output:

Print the answer corresponding to each query in a new line.

Constraints:

  • 1N103
  • 1M5104
  • 1Ai103
  • 1LR106

Sample Input
8 3
2 2 4 2 6 1 5 7
6 20
8 12
2 15
Sample Output
197
63
143
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

For query 2, L=8 and R=12. There are 10 subsets with sum of their elements as 8, 13 subsets with sum of their elements as 9, 12 subsets with sum of their elements as 10, 14 subsets with sum of their elements as 11 and 14 subsets with sum of their elements as 12. So, the answer to the query is 10 + 13 + 12 + 14 + 14 = 63 mod (109+7) = 63.

Editor Image

?