J. The Big Ticket
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The biggest football game of the year is almost here, and exactly one ticket remains. There are $$$n$$$ people hoping to receive it.

The organizer assigns each person a positive relative weight. If the relative weights are $$$w_1,w_2,\ldots,w_n$$$, then the probability that person $$$i$$$ receives the ticket is

$$$$$$\frac{w_i}{\sum_{j=1}^{n}w_j}.$$$$$$

Rather than storing the weights directly, the organizer stores $$$n-1$$$ ratios $$$a_1,\ldots,a_{n-1}$$$. For each $$$1\le i \lt n$$$, person $$$i$$$ is $$$a_i$$$ times as likely to receive the ticket as person $$$i+1$$$. Equivalently, their weights satisfy

$$$$$$w_i=a_iw_{i+1}.$$$$$$

The ratios change over time. You must process $$$q$$$ queries:

  • 1 i x: Set $$$a_i$$$ to $$$x$$$.
  • 2 i: Find the probability that person $$$i$$$ receives the ticket.
Input

The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2\le n\le 2\cdot10^5$$$, $$$1\le q\le2\cdot10^5$$$) — the number of people and the number of queries, respectively.

The second line contains $$$n-1$$$ integers $$$a_1,a_2,\ldots,a_{n-1}$$$ ($$$1\le a_i \lt 10^9+7$$$) — the initial likelihood ratios between consecutive people.

Each of the next $$$q$$$ lines describes a query in one of the following formats:

  • 1 i x ($$$1\le i \lt n$$$, $$$1\le x \lt 10^9+7$$$) — Set $$$a_i$$$ to $$$x$$$.
  • 2 i ($$$1\le i\le n$$$) — Find the probability that person $$$i$$$ receives the ticket.
Output

For each query of the second form, let the requested probability be $$$\frac{p}{r}$$$. If $$$r$$$ is divisible by $$$10^9+7$$$, print $$$\texttt{-1}$$$. Otherwise, print

$$$$$$p\cdot r^{-1}\bmod (10^9+7),$$$$$$

where $$$r^{-1}$$$ is the modular multiplicative inverse of $$$r$$$ modulo $$$10^9+7$$$.

Example
Input
4 5
2 3 4
2 1
2 4
1 2 1
2 1
2 3
Output
804878055
658536590
823529418
411764709
Note

Initially, choose $$$w_4=1$$$. Then the relative weights are $$$(24,12,4,1)$$$ and their sum is $$$41$$$. Thus, the first two queried probabilities are $$$\frac{24}{41}$$$ and $$$\frac{1}{41}$$$.

After setting $$$a_2=1$$$, the weights become $$$(8,4,4,1)$$$ with sum $$$17$$$. The final two queried probabilities are $$$\frac{8}{17}$$$ and $$$\frac{4}{17}$$$.