题目描述
华清大学内有一个彩票站点,站点内设有 n 个彩箱。初始时每个彩箱内都放有若干奖券,奖券分为中奖券与空奖券两种,其中第 i 个彩箱内有 ai 张中奖券、bi 张空奖券。同学们每次抽奖时,将会选择一个彩箱,然后从该彩箱剩余的奖券中等概率随机抽取一张,即剩余的每张奖券被抽中的概率均相等。注意:被抽出的奖券将不放回彩箱。
现在有 m 位同学在彩票站点排队,同学们将依次每人进行一次操作。具体地,对于第 j 个操作的同学,他可能进行的操作有以下三种:
- 抽奖:从第 lj 个到第 rj 个彩箱,对它们中的每个都连续抽取 cj 次奖。若彩箱中剩余奖券数量不足 cj,则将彩箱中所有奖券抽完为止。
- 询问:从第 xj 个到第 yj 个彩箱,求所有被抽出的中奖券的数量之和的期望值。
- 加奖:在第 pj 个彩箱中,添加 uj 张中奖券和 vj 张空奖券。
现在请你回答同学们的每次询问。由题目性质知,期望值一定可以写成 qp 形式的有理数,请你输出它对 109+7(一个质数)取模后的结果,即找出一个 r (0≤r<109+7) 使得 qr≡p(mod109+7)。可以证明这样的 r 是唯一的。
输入格式
第一行两个正整数 n,m,分别表示彩箱数和同学人数。
接下来 n 行,每行描述一个彩箱。
这 n 行中的第 i 行有两个整数 ai,bi,意义见题目描述。
接下来 m 行,每行描述一个同学的操作。
这 m 行中的第 j 行的第一个整数 opj 表示操作类型。若 opj=1,接下来输入三个整数 lj,rj,cj;若 opj=2,接下来输入两个整数 xj,yj;若 opj=3,接下来输入三个整数 pj,uj,vj。具体变量意义见题目描述。
同一行内整数均由一个空格分隔开。
输入数据保证:
0≤ai,bi,cj≤108
0≤uj,vj≤103
1≤lj≤rj≤n
1≤xj≤yj≤n
1≤pj≤n
opj∈{1,2,3}
输出格式
对于每个 opj=2 的询问,输出一行一个整数表示询问的答案。
提示
【样例解释 1】
第一位同学操作后,第 1 个彩箱中被抽出的中奖券数量期望值为 31。
第二位同学操作后,第 2 个彩箱中被抽出的中奖券数量期望值为 21。
第三位同学的答案即为:31+21=65,它对 109+7 取模的结果为 833333340。
第四位同学操作后,第 3 个彩箱中有 3 张中奖券、1 张空奖券。
第五位同学操作后,第 3 个彩箱中被抽出的中奖券数量期望值为 49。
第六位同学的答案即为:31+21+49=1237,它对 109+7 取模的结果为 83333337。
【样例 2】
见题目附件中 2.in/2.ans
。
【样例 3】
见题目附件中 3.in/3.ans
。
【样例 4】
见题目附件中 4.in/4.ans
。
【子任务】
子任务编号 |
分值 |
n,m≤ |
其他限制 |
1 |
23 |
1000 |
0≤ai,bi≤10 且 opj=3 |
2 |
17 |
105 |
opj=3 且 lj=rj |
3 |
20 |
2×105 |
lj=rj |
4 |
opj=3 |
5 |
3×105 |
无 |