On Yarn Street, there are $N$ stores numbered from $1$ to $N$, each selling a single item with cost $c_i$. Throughout the day, $M$ shoppers walk along different segments of the street. The $i$-th shopper will buy one item from each store numbered from $l_i$ to $r_i$.

The local association offers coupons of value $p$ to attract shoppers. The $i$-th shopper gets $k_i$ coupons. The coupons have specific stipulations:

• Each coupon can only be used once.
• At most one coupon can be used on each item, per shopper.
• The coupon can only be redeemed for items whose price are divisible by $p$.
• Upon redemption, the item's price is divided by $p$.

Shoppers aim to minimize the product of the total costs of items they purchase. For example, if a shopper purchases items with costs $2$, $3$, and $7$, the product of the total costs is $2\times 3\times 7=42$.

Your job is to assist each shopper in finding the minimum cost of their shopping trip if they are able to choose the optimal value of $p$. Note that a coupon's price reduction only applies to the shopper who used them, and that not all coupons have to be used.

Constraints

For all subtasks:

$1\le N\le 3\times {10}^5$

$1\le M\le 5\times {10}^4$

$1\le c_i\le {10}^6$

$1\le l\le r\le N$

$1\le k\le 10$

Subtask 1 [20%]

$1\le N\le 5\times {10}^4$

$1\le c_i\le {10}^5$

Subtask 2 [30%]

$1\le N\le {10}^5$

Subtask 3 [50%]

No additional constraints.

Input Specification

The first line contains an integer $N$, the number of stores on Yarn Street.

The second line contains $N$ integers $c_i$, indicating the cost of the item at each store.

The third line contains an integer $M$, the number of shoppers.

The next $M$ lines each contain three integers, $l_i$, $r_i$, and $k_i$, indicating that shopper $i$ travels from store $l$ to store $r$ with $k_i$ coupons.

Output Specification

For each of the $M$ people, find the minimal possible product and output that mod ${10}^9+7$.

Sample Input

5
6 15 25 20 30
3
1 3 2
2 5 1
2 5 4

Sample Output

90
7500
360

Sample Explanation

The first person goes from store $1$ to store $3$. The prices are $6$, $15$, and $25$. By choosing $p=5$ and using coupons on items $2$ and $3$, the prices become $6$, $3$, and $5$. This leads to a minimal product of $90$.

The second person goes from store $2$ to store $5$.The prices are $15$, $25$, $20$, and $30$. By choosing $p=30$ and using coupons on the item $5$, the prices become $15$, $25$, $20$, and $1$, leading to a minimal product of $7500$.

The third person also goes from store $2$ to store $5$. The prices are $15$, $25$, $20$, and $30$. By choosing $p=5$ and using coupons on items $2$, $3$, $4$ and $5$, the prices become $3$, $5$, $4$, and $6$, leading to a minimal product of $360$.