P10338 [THUSC 2019] 彩票

华清大学内有一个彩票站点，站点内设有 $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$ 的询问，输出一行一个整数表示询问的答案。

**【样例解释 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 | 20 | $2 \times 10^5$ | $op_j \neq 3$ | | 5 | 20 | $3 \times 10^5$ | 无 |