Distribution of Relief

"Please follow all instructions provided by your local health authorities."

Due to Coronovirus epidemic everywhere is lockdown. For this reason many people troubling with their survival.
Tanima Hossain, a famous programmer wants to give some relief to the people who are troubling with livelihood of his village. So he collect a list of families who required relief from his friends. In the list he has the informations of a special required point(He will give relief according to this information). Every different day he will give relief to different ranges of families. (Suppose there are 5 families in his village. In first day he can give relief to 1st to 5th families; In second day he can give relief to 2nd to 4th families).There is a condition for giving relief. The amount he will provide every single day for relief will be lowest common multiple of the special required points that will get the relief in the corresponding day.

Suppose there are 5 families in his village. The number of special required points are 2,4,6,8,10. Suppose first day he will give relief to 2nd to 4th families. So the amount of relief in first day will be 24 (lowest common multiple of 4,6,8)

Input

First line will be contain the number of families N. (1<=N<=1e4)
Next line will be contain N space separated integers containing the special required point Ai (1<=Ai<=1e6)

Next line wil be contain Q, which denotes number of days. (1<=Q<=1e4)
Next Q lines will be contained Li and Ri which dentotes the range of the families that will get relief on the corresponding day. (1<=Li<=Ri<=N)

Output

Q lines of output. Every line will be contain the lowest common multiple of special required point of the given range for the corresponding day. As the answer can be very big so you have to print the mod lowest common multiple of special numbers with 1e9+7.

Sample

Input	Output
5 2 4 6 8 10 4 1 5 2 4 3 5 3 4	120 24 120 24