#P6496. [ABC242Ex] Random Painting
[ABC242Ex] Random Painting
[ABC242Ex] Random Painting
题目描述
有 个小球,一开始标号为 ,每个对应一个区间 。有 个方块,标号 ,初始时无色。重复以下步骤直到所有的方块都被涂色:
- 等概率随机拿出一个小球 ,每次抽取相互独立
- 将 涂色
- 将小球放回去
每次完成上述三步算作一次操作。求直到所有方块都被涂色时的操作次数的期望,对 取模。已经涂色的方块再次被涂色不影响状态。
保证 ,,且每个方块至少被一个给定区间覆盖。
输入格式
从标准输入读入。
第一行包含两个整数 。
接下来 行,第 行包含两个整数 ,表示第 个小球对应的涂色区间。
输出格式
向标准输出输出所求期望对 取模的结果。
若所求概率或期望为既约分数 ,输出满足 的唯一整数 。本题约束保证分母在该模数下可逆。
样例 #1
样例输入 #1
3 3
1 1
1 2
2 3
样例输出 #1
499122180
样例 #2
样例输入 #2
13 10
3 5
5 9
3 12
1 13
9 11
12 13
2 4
9 12
9 11
7 11
样例输出 #2
10
样例 #3
样例输入 #3
100 11
22 43
84 93
12 71
49 56
8 11
1 61
13 80
26 83
23 100
80 85
9 89
样例输出 #3
499122193
样例 1 说明
所求期望为 ,由于 ,输出 。