Range product queries

You are given a sequence of $N$ numbers. Elements of the sequence change often, and between those changes you have to compute the product of some range.

For example, take the sequence 1, 2, 3, 4, 5. Change the third number to 6 and ask for the product from the second number to the fifth, and the answer is 240. Then change the fifth number to 2 and ask for the product from the third number to the fifth, and the answer is 48.

Given changes and range product queries mixed together, write a program that computes the product for each query.

The first line contains the count of numbers $N$ ($1 \le N \le 1{,}000{,}000$), the number of changes $M$ ($1 \le M \le 10{,}000$), and the number of range product queries $K$ ($1 \le K \le 10{,}000$), separated by spaces.

The next $N$ lines contain the elements of the sequence in order, one per line.

The following $M + K$ lines each contain three integers $a$, $b$, and $c$. If $a$ is 1, change the $b$-th number to $c$. If $a$ is 2, compute the product from the $b$-th number to the $c$-th number. On a line where $a$ is 2, $b \le c$ holds.

Every number in the input is an integer between 0 and 1,000,000, inclusive.

Print one line for each product query, in the order the queries are given, for a total of $K$ lines. Each line holds the product of that range modulo 1,000,000,007.