#P18895. [2026多校联测]挂科

[2026多校联测]挂科

题目描述

期末考试完后感觉挂科了,怎么办,先求捞捞。

具体来说,考试共有 10910^9 道题,小 W 做了 nn 场梦,第 ii 场梦梦到了他所做的所有编号在区间 [li,ri)[l_i,r_i) 之中的题全都爆零了!\textbf{注意这里是开区间,不包含} rir_i。

醒来之后小 W 感觉真的要挂科了,于是再睡了一觉,并发现了一对数字 a,b(a≤b)a,b(a \leq b)。这对数字的含义是:等概率选择一个区间 [c,d]⊆[a,b][c,d] \subseteq [a,b],并让编号 [c,d][c,d] 之间的梦变成真实的,即一道题 kk 爆零当且仅当存在梦境 p∈[c,d]p \in [c,d] 使得 k∈[lp,rp)k \in [l_p,r_p)。小 W 想知道自己期望爆零多少题。

由于小 W 很困,所以小 W 会再睡 mm 次觉,每次会给你一个 ai,bia_i,b_i,你需要计算当 a=ai,b=bia=a_i,b=b_i 时的期望爆零题数。只需要输出对 109+710^9+7 取模的结果。

输入格式

第一行两个数字 n,mn,m,表示梦境的个数以及计算的次数。

接下来 nn 行,每行两个正整数 li,ril_i,r_i 表示一场梦境。

接下来 mm 行每行两个正整数 ai,bia_i,b_i 表示一次计算。

输出格式

输出共 mm 行,每行一个整数表示答案对 109+710^9+7 取模的结果。

样例 1 输入

3 3
1 3
2 4
3 5
1 3
1 2
2 3

样例 1 输出

666666674
333333338
333333338

样例 1 解释

对于样例 11,记 f(l,r)f(l,r) 表示若 [l,r][l,r] 里的梦境都是真实的会爆零多少题。

则 $f(1,1)=2,f(1,2)=3,f(1,3)=4,f(2,2)=2,f(2,3)=3,f(3,3)=2$。

因此第一次询问答案为 16(2+3+4+2+3+2)=83\frac{1}{6}(2+3+4+2+3+2)=\frac{8}{3}。

第二次询问答案为 13(2+3+2)=73\frac{1}{3}(2+3+2)=\frac{7}{3},第三次询问答案一样。

样例 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):n,m≤100n,m \leq 100

  • Subtask2(20 points):n,m≤1000n,m \leq 1000

  • Subtask3(25 points):n,m≤50000n,m \leq 50000

  • Subtask4(35 points):无特殊限制。