Sequence Queries and Modular Products

You are given an initial sequence of integers and a series of queries to process. There are two types of queries:

• Type 1: Append an integer X to the end of the sequence.
• Type 2: Compute the product of a subarray from index L to R (inclusive) modulo 10^9+7. Formally, you need to evaluate $$\prod_{i=L}^{R} a_i \bmod 1000000007.$$

All indices are 1-indexed.

Your task is to process all queries in the order given. For each query of type 2, output the computed product on a new line.

inputFormat

The input is given from stdin in the following format:

1. An integer n indicating the number of elements in the initial sequence.
2. n space-separated integers representing the initial sequence.
3. An integer q representing the number of queries.
4. q lines, each representing a query in one of the following formats:
• 1 X — Append integer X to the sequence.
• 2 L R — Compute the product of the subarray from index L to R modulo 1000000007.

outputFormat

For each query of type 2, output the result on its own line to stdout.

## sample

5
2 3 5 7 11
4
2 1 3
1 13
2 1 6
2 4 6

30
30030
1001

</p>