Background

Problem Description

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.

You may use the sample explanation to better understand the statement.

Input Format

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.

Output Format

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

5 4
48 52 8 27 34 
3 4 3 2 2 
2 2 3
2 1 5
1 1 34 4
2 1 3

72
133333711
333333468

Hint

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

For all testdata, $1\le n,m\le 10^5$, $0<a_i<10^9+7$, $1<b_i<10^9+7$. All operations are guaranteed to be valid, and all inputs are guaranteed to be integers.

Translated by ChatGPT 5