题目背景

题目描述

你手中有一个数字 $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 有理数取余。

可参考样例解释理解题意。

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数，第 $i$ 个整数代表 $a_i$。

第三行 $n$ 个整数，第 $i$ 个整数代表 $b_i$。

后 $m$ 行每行描述一次操作，格式见题目描述。

输出格式

对于每个询问，输出对应的期望。答案对 $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

提示

样例解释

对于第一次询问，令 $f(i,j)$ 为你从 $i$ 开始顺次走到 $j$ 后手中的数的最大值，则答案为 $\frac{1}{3}[f(2,2)+f(2,3)+f(3,3)]=\frac{1}{3}(52+156+8)=72$。

数据范围

对于所有数据，$1\le n,m\le 10^5$，$0<a_i<10^9+7$，$1<b_i<10^9+7$，保证操作合法，保证所有输入均为整数。