『STA - R5』ReLyna
题目背景
题目描述
你手中有一个数字 $x$。走到位置 $i$ 时你可以将手中的数字变为 $x+a_i$ 或 $x\times b_i$。
有 $m$ 次操作。
- `1 x y z`，执行 $a_x\gets y$，$b_x\gets z$。
- `2 l r`，查询若你从 $[l,r]$ 的所有子区间中等概率选择一个子区间 $[l',r']$，则你从 $l'$ 走到 $r'$ 后手中的数的最大值的期望是多少？答案对 $10^9+7$ 取模。每次行动开始前你手中的数字都会归零。
如果你不知道有理数如何取模，可以参考 [P2613 有理数取余](https://www.luogu.com.cn/problem/P2613)。
可参考样例解释理解题意。
输入输出格式
输入格式
第一行两个整数 $n,m$。
第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。
第三行 $n$ 个整数，第 $i$ 个整数代表 $b_i$。
后 $m$ 行每行描述一次操作，格式见题目描述。
输出格式
对于每个询问，输出对应的期望。答案对 $10^9+7$ 取模。
输入输出样例
输入样例 #1
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
输出样例 #1
72
133333711
333333468说明
**样例解释**
对于第一次询问，令 $f(i,j)$ 为你从 $i$ 开始顺次走到 $j$ 后手中的数的最大值，则答案为 $\frac{1}{3}[f(2,2)+f(2,3)+f(3,3)]=\frac{1}{3}(52+156+8)=72$。
**数据范围**
| 子任务编号 | $n$ | $m$ | 特殊性质 | 分值 |
| :-----------: | :-----------: | :-----------: | :-----------: | :-----------: |
| Subtask #1 | $50$ | $50$ | 无 | 5 |
| Subtask #2 | $500$ | $500$ | 无 | 5 |
| Subtask #3 | $10^5$ | $10^5$ | 保证任何时刻 $a_i=1$ | 25 |
| Subtask #4 | $10^5$ | $50$ | 无 | 25 |
| Subtask #5 | $10^5$ | $10^5$ | 没有修改操作 | 25 |
| Subtask #6 | $10^5$ | $10^5$ | 无 | 15 |
对于所有数据，$1\le n,m\le 10^5$，$0<a_i<10^9+7$，$1<b_i<10^9+7$，保证操作合法，保证所有输入均为整数。