The king wants to eat a feast.

The food items will be placed in front of the king in a row, and the king eats the food items in the sequence (left to right) one by one.

He wants to eat different food items in groups of different sizes.

There are $N$ food items and an array $A$ consisting of $N$ elements, where $A_i$ denotes the size of the group in which the king wants to eat the $i^{th}$ food item.

Note:-

•  The $i^{th}$ food item can only be served in multiples of $A_i$ at once, and no other serving combinations are allowed.

Also, the king wants to eat food items in a particular range only.

There would be $Q$ queries, each containing two integers $X_i$ and $Y_i$, denoting the minimum and maximum number of food items that the king wants to eat.

For each query, you need to calculate the total number of ways in which you can create a feast by arranging the food items in such a way that the king gets to eat the food items in groups of sizes desired by him, and the total food items eaten are between $X_i$ and $Y_i$ (both inclusive).

The answer should be reported as modulo $10^9+7$ as the number of feasts can be large.

Input Format:

• The first line contains an integer $N$, the number of food items.
• The second line contains $N$ space-separated integers  denoting the array $A$.
• The third line contains an integer $Q$, the number of queries.
• The next $Q$ lines contain two space-separated integers $X_i$ and $Y_i$, denoting the minimum and maximum number of food items the king wants to eat for that query, both inclusive.

Output Format:

• For each query, output the total number of ways in which the king can eat a feast, satisfying the given conditions. Output the result modulo $10^9+7$

Constraints:

$1 \leq N \leq 100 \\ 1 \leq A_i \leq 10^5 \\ 1 \leq Q \leq 10^5 \\ 1 \leq X_i, Y_i \leq 10^5 \\ X_i \leq Y_i$