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 \(10^{9}\) + 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 \(\in\) [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:

• \(1 ≤ N ≤ 10^{3}\)
• \(1 ≤ M ≤ 5 * 10^{4}\)
• \(1 ≤ A_{i} ≤ 10^{3}\)
• \(1 ≤ L ≤ R ≤ 10^{6}\)