#P18895. [2026多校联测]挂科
[2026多校联测]挂科
题目描述
期末考试完后感觉挂科了,怎么办,先求捞捞。
具体来说,考试共有 道题,小 W 做了 场梦,第 场梦梦到了他所做的所有编号在区间 之中的题全都爆零了!\textbf{注意这里是开区间,不包含} 。
醒来之后小 W 感觉真的要挂科了,于是再睡了一觉,并发现了一对数字 。这对数字的含义是:等概率选择一个区间 ,并让编号 之间的梦变成真实的,即一道题 爆零当且仅当存在梦境 使得 。小 W 想知道自己期望爆零多少题。
由于小 W 很困,所以小 W 会再睡 次觉,每次会给你一个 ,你需要计算当 时的期望爆零题数。只需要输出对 取模的结果。
输入格式
第一行两个数字 ,表示梦境的个数以及计算的次数。
接下来 行,每行两个正整数 表示一场梦境。
接下来 行每行两个正整数 表示一次计算。
输出格式
输出共 行,每行一个整数表示答案对 取模的结果。
样例 1 输入
3 3
1 3
2 4
3 5
1 3
1 2
2 3
样例 1 输出
666666674
333333338
333333338
样例 1 解释
对于样例 ,记 表示若 里的梦境都是真实的会爆零多少题。
则 $f(1,1)=2,f(1,2)=3,f(1,3)=4,f(2,2)=2,f(2,3)=3,f(3,3)=2$。
因此第一次询问答案为 。
第二次询问答案为 ,第三次询问答案一样。
样例 2
见大样例。
数据范围
本题采用捆绑测试,只有通过一个 Subtask 内的所有数据才能获得这个 Subtask 的所有分数
对于所有数据:$1 \leq n,m \leq 2 \times 10^5, 1 \leq l_i < r_i \leq 10^9, 1 \leq a_i \leq b_i \leq n$。
-
Subtask1(20 points):
-
Subtask2(20 points):
-
Subtask3(25 points):
-
Subtask4(35 points):无特殊限制。