P10399 『STA - R5』ReLyna


You have a number $x$ in your hand. When you arrive at position $i$, you may change the number in your hand to $x+a_i$ or $x\times b_i$. There are $m$ operations. - `1 x y z`: set $a_x\gets y$, $b_x\gets z$. - `2 l r`: query the following. If you choose a subsegment $[l',r']$ uniformly at random from all subsegments of $[l,r]$, what is the expected value of the maximum possible number in your hand after you walk from $l'$ to $r'$? Output the answer modulo $10^9+7$. Before each walk starts, the number in your hand is reset to $0$. If you do not know how to take a rational number modulo a prime, you may refer to [P2613 Taking Remainder of Rational Numbers](https://www.luogu.com.cn/problem/P2613). You may use the sample explanation to better understand the statement.

The first line contains two integers $n,m$. The second line contains $n$ integers, where the $i$-th integer denotes $a_i$. The third line contains $n$ integers, where the $i$-th integer denotes $b_i$. The next $m$ lines each describe one operation. The format is given in the description.

For each query, output the corresponding expectation. The answer should be taken modulo $10^9+7$.

**Sample Explanation** For the first query, let $f(i,j)$ be the maximum possible number in your hand after you start from $i$ and walk sequentially to $j$. Then the answer is $\frac{1}{3}[f(2,2)+f(2,3)+f(3,3)]=\frac{1}{3}(52+156+8)=72$. **Constraints** | Subtask ID | $n$ | $m$ | Special Property | Score | | :-----------: | :-----------: | :-----------: | :-----------: | :-----------: | | Subtask #1 | $50$ | $50$ | None | 5 | | Subtask #2 | $500$ | $500$ | None | 5 | | Subtask #3 | $10^5$ | $10^5$ | Guaranteed that at any time $a_i=1$ | 25 | | Subtask #4 | $10^5$ | $50$ | None | 25 | | Subtask #5 | $10^5$ | $10^5$ | No modification operations | 25 | | Subtask #6 | $10^5$ | $10^5$ | None | 15 | For all testdata, $1\le n,m\le 10^5$, $0