{"problem":{"name":"[THUSC 2019] 彩票","description":{"content":"华清大学内有一个彩票站点，站点内设有 $n$ 个彩箱。初始时每个彩箱内都放有若干奖券，奖券分为中奖券与空奖券两种，其中第 $i$ 个彩箱内有 $a_i$ 张中奖券、$b_i$ 张空奖券。同学们每次抽奖时，将会选择一个彩箱，然后从该彩箱剩余的奖券中等概率随机抽取一张，即剩余的每张奖券被抽中的概率均相等。注意：被抽出的奖券将不放回彩箱。 现在有 $m$ 位同学在彩票站点排队，同学们将依次每人进行一次","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1500,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10338"},"statements":[{"statement_type":"Markdown","content":"华清大学内有一个彩票站点，站点内设有 $n$ 个彩箱。初始时每个彩箱内都放有若干奖券，奖券分为中奖券与空奖券两种，其中第 $i$ 个彩箱内有 $a_i$ 张中奖券、$b_i$ 张空奖券。同学们每次抽奖时，将会选择一个彩箱，然后从该彩箱剩余的奖券中等概率随机抽取一张，即剩余的每张奖券被抽中的概率均相等。注意：被抽出的奖券将不放回彩箱。\n\n现在有 $m$ 位同学在彩票站点排队，同学们将依次每人进行一次操作。具体地，对于第 $j$ 个操作的同学，他可能进行的操作有以下三种：\n\n1. 抽奖：从第 $l_j$ 个到第 $r_j$ 个彩箱，对它们中的每个都连续抽取 $c_j$ 次奖。若彩箱中剩余奖券数量不足 $c_j$，则将彩箱中所有奖券抽完为止。\n2. 询问：从第 $x_j$ 个到第 $y_j$ 个彩箱，求所有被抽出的中奖券的数量之和的期望值。\n3. 加奖：在第 $p_j$ 个彩箱中，添加 $u_j$ 张中奖券和 $v_j$ 张空奖券。\n\n现在请你回答同学们的每次询问。由题目性质知，期望值一定可以写成 $\\frac{p}{q}$ 形式的有理数，请你输出它对 $10^9+7$（一个质数）取模后的结果，即找出一个 $r$ $(0\\leq r < 10^9+7)$ 使得 $qr \\equiv p \\pmod{10^9+7}$。可以证明这样的 $r$ 是唯一的。\n\n## Input\n\n第一行两个正整数 $n,m$，分别表示彩箱数和同学人数。\n\n接下来 $n$ 行，每行描述一个彩箱。\n\n这 $n$ 行中的第 $i$ 行有两个整数 $a_i,b_i$，意义见题目描述。\n\n接下来 $m$ 行，每行描述一个同学的操作。\n\n这 $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$。具体变量意义见题目描述。\n\n同一行内整数均由一个空格分隔开。\n\n输入数据保证：\n\n$0 \\leq a_i,b_i,c_j \\leq 10^8$\n\n$0\\leq u_j,v_j \\leq 10^3$\n\n$1\\leq l_j\\leq r_j \\leq n$\n\n$1\\leq x_j\\leq y_j\\leq n$\n\n$1\\leq p_j\\leq n$\n\n$op_j \\in \\{1,2,3\\}$\n\n## Output\n\n对于每个 $op_j = 2$ 的询问，输出一行一个整数表示询问的答案。\n\n[samples]\n\n## Note\n\n**【样例解释 1】**\n\n第一位同学操作后，第 1 个彩箱中被抽出的中奖券数量期望值为 $\\frac{1}{3}$。\n\n第二位同学操作后，第 2 个彩箱中被抽出的中奖券数量期望值为 $\\frac{1}{2}$。\n\n第三位同学的答案即为：$\\frac{1}{3} + \\frac{1}{2} = \\frac{5}{6}$，它对 $10^9+7$ 取模的结果为 $833333340$。\n\n第四位同学操作后，第 3 个彩箱中有 3 张中奖券、1 张空奖券。\n\n第五位同学操作后，第 3 个彩箱中被抽出的中奖券数量期望值为 $\\frac{9}{4}$。\n\n第六位同学的答案即为：$\\frac{1}{3} + \\frac{1}{2} + \\frac{9}{4} = \\frac{37}{12}$，它对 $10^9+7$ 取模的结果为 $83333337$。\n\n**【样例 2】**\n\n见题目附件中 `2.in/2.ans`。\n\n**【样例 3】**\n\n见题目附件中 `3.in/3.ans`。\n\n**【样例 4】**\n\n见题目附件中 `4.in/4.ans`。\n\n**【子任务】**\n\n| 子任务编号| 分值 | $n,m\\leq$ | 其他限制 |\n| :--: | :--: | :--: | :--: |\n| 1 | 23 | $1000$ | $0\\leq a_i,b_i \\leq 10$ 且 $op_j \\neq 3$|\n| 2 | 17 | $10^5$ | $op_j \\neq 3$ 且 $l_j = r_j$ |\n| 3 | 20 | $2 \\times 10^5$ | $l_j=r_j$ |\n| 4 | 20 | $2 \\times 10^5$ | $op_j \\neq 3$ |\n| 5 | 20 | $3 \\times 10^5$ | 无 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10338","tags":["2019","THUSC"],"sample_group":[["3 6\n1 2\n2 2\n2 0\n1 1 1 1\n1 2 2 1\n2 1 3\n3 3 1 1\n1 3 3 3\n2 1 3\n","833333340\n83333337\n"]],"created_at":"2026-03-03 11:09:25"}}