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~.