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 + 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 and are considered different if there exist at least one index i that belongs to but does not belong to 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:
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 (+7) = 63.