配点: 100 点
問題文
为了参加舞蹈编程祭「KACoder」,Nukesu君已经完成了预赛。 Q 我决定喝几天神仙混合果汁,据说对身体有好处。
妖精 1 鸡翅的“美味度”用正整数来表示,混合汁的“美味度”则是仙女食材的美味度之和。
你 i 当天早上 A_i 以上 B_i 以下每一个整数美味仙女 1 购买每根羽毛,1 至少选择鸡翅并将其添加到混合器中。为了保证新鲜度,未使用的仙女当晚就被丢弃,不再使用。
此时,i 你第一天做的混合果汁的美味程度有多少种可能的值?答案可能非常大,所以10^9+7 后的余数。
入力
输入由标准输入给出,如下所示。
Q A_1 B_1 A_2 B_2 ... A_Q B_Q
- 1 行显示距离资格赛还有多少天。 越过 Q 。 对于
- 2 从行 Q 线,i+1 在线 i 首日上午需购买的仙女资料 A_i, B_i 。 对于
出力
总而言之
需要 Q 行。
列出
i 行中,i 问题的答案。
制約
- 1 \leq Q \leq 100000
- 1 \leq A_i \leq B_i \leq 10^{9}
- 所有输入均为整数
小課題
小課題 1 [7 点]
- Q = 1 很满意。
- B_1 - A_1 \leq 20 很满意。
小課題 2 [60 点]
- B_i - A_i 的总和是 不超过 10^6 。
小課題 3 [33 点]
- 没有其他限制。
入力例 1
4 1 3 3 7 4 7 3141592 3141592
出力例 1
6 21 14 1
例如,3 天仙的美味是 4, 5, 6, 7 。这几天之一 1 如何选择多个 15 混合果汁有多种类型,每种都有各自的美味。
- 4, 5, 6, 7, 4+5, 4+6, 5+6, 4+7, 5+7, 6+7, 4+5+6, 4+5+7, 4+6+7, 5+6+7, 4+5+6+7
但最终 仅 5+6 和 按字典顺序比较 4+7 仅有的 11 相同,因此美味的可能值为 14 方法有很多。