题目描述

华清大学内有一个彩票站点，站点内设有 $n$ 个彩箱。初始时每个彩箱内都放有若干奖券，奖券分为中奖券与空奖券两种，其中第 $i$ 个彩箱内有 $a_i$ 张中奖券、$b_i$ 张空奖券。同学们每次抽奖时，将会选择一个彩箱，然后从该彩箱剩余的奖券中等概率随机抽取一张，即剩余的每张奖券被抽中的概率均相等。注意：被抽出的奖券将不放回彩箱。

现在有 $m$ 位同学在彩票站点排队，同学们将依次每人进行一次操作。具体地，对于第 $j$ 个操作的同学，他可能进行的操作有以下三种：

1. 抽奖：从第 $l_j$ 个到第 $r_j$ 个彩箱，对它们中的每个都连续抽取 $c_j$ 次奖。若彩箱中剩余奖券数量不足 $c_j$，则将彩箱中所有奖券抽完为止。
2. 询问：从第 $x_j$ 个到第 $y_j$ 个彩箱，求所有被抽出的中奖券的数量之和的期望值。
3. 加奖：在第 $p_j$ 个彩箱中，添加 $u_j$ 张中奖券和 $v_j$ 张空奖券。

现在请你回答同学们的每次询问。由题目性质知，期望值一定可以写成 $\frac{p}{q}$ 形式的有理数，请你输出它对 $10^9+7$（一个质数）取模后的结果，即找出一个 $r$ $(0\leq r < 10^9+7)$ 使得 $qr \equiv p \pmod{10^9+7}$。可以证明这样的 $r$ 是唯一的。

输入格式

第一行两个正整数 $n,m$，分别表示彩箱数和同学人数。

接下来 $n$ 行，每行描述一个彩箱。

这 $n$ 行中的第 $i$ 行有两个整数 $a_i,b_i$，意义见题目描述。

接下来 $m$ 行，每行描述一个同学的操作。

这 $m$ 行中的第 $j$ 行的第一个整数 $op_j$ 表示操作类型。若 $op_j=1$，接下来输入三个整数 $l_j,r_j,c_j$；若 $op_j = 2$，接下来输入两个整数 $x_j,y_j$；若 $op_j=3$，接下来输入三个整数 $p_j,u_j,v_j$。具体变量意义见题目描述。

同一行内整数均由一个空格分隔开。

输入数据保证：

$0 \leq a_i,b_i,c_j \leq 10^8$

$0\leq u_j,v_j \leq 10^3$

$1\leq l_j\leq r_j \leq n$

$1\leq x_j\leq y_j\leq n$

$1\leq p_j\leq n$

$op_j \in \{1,2,3\}$

输出格式

对于每个 $op_j = 2$ 的询问，输出一行一个整数表示询问的答案。

3 6
1 2
2 2
2 0
1 1 1 1
1 2 2 1
2 1 3
3 3 1 1
1 3 3 3
2 1 3

833333340
83333337

提示

【样例解释 1】

第一位同学操作后，第 1 个彩箱中被抽出的中奖券数量期望值为 $\frac{1}{3}$。

第二位同学操作后，第 2 个彩箱中被抽出的中奖券数量期望值为 $\frac{1}{2}$。

第三位同学的答案即为：$\frac{1}{3} + \frac{1}{2} = \frac{5}{6}$，它对 $10^9+7$ 取模的结果为 $833333340$。

第四位同学操作后，第 3 个彩箱中有 3 张中奖券、1 张空奖券。

第五位同学操作后，第 3 个彩箱中被抽出的中奖券数量期望值为 $\frac{9}{4}$。

第六位同学的答案即为：$\frac{1}{3} + \frac{1}{2} + \frac{9}{4} = \frac{37}{12}$，它对 $10^9+7$ 取模的结果为 $83333337$。

【样例 2】

见题目附件中 2.in/2.ans。

【样例 3】

见题目附件中 3.in/3.ans。

【样例 4】

见题目附件中 4.in/4.ans。

【子任务】

子任务编号	分值	$n,m\leq$	其他限制
1	23	$1000$	$0\leq a_i,b_i \leq 10$ 且 $op_j \neq 3$
2	17	$10^5$	$op_j \neq 3$ 且 $l_j = r_j$
3	20	$2 \times 10^5$	$l_j=r_j$
4			$op_j \neq 3$
5		$3 \times 10^5$	无