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:
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:
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$$$.
4 52 3 42 12 41 2 12 12 3
804878055 658536590 823529418 411764709
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}$$$.
