Problem Description
"看似随机,实则早已注定"——光羽
度度熊有n个随机变量x1,x2,...,xn。给定区间[l1,r1],...,[ln,rn],变量xi的值会**等概率**成为区间[li,ri]中的任意一个**整数**。
显然这n个随机变量的值会有一共∏ni=1(ri−li+1) 种情况,且每种情况出现的概率为∏ni=11ri−li+1 。
对于某种情况,令h=max{x1,x2,...,xn},定义这种情况的**权值**为:∏ni=1(h−xi+1).
度度熊想知道权值的**期望**是多少?请将答案对109+7取模后输出。
PS:不清楚期望是啥?为什么不问问神奇的百度呢?
Input
第一行一个数,表示数据组数T。
每组数据第一行一个整数n;接下来n行,每行两个数,表示li和ri。
数据组数T=100,满足:
- 1≤n≤100
- 1≤li≤ri≤104
其中70%的数据满足ri≤100。
Output
每组数据输出一行,每行仅包含一个数,表示期望。
假设答案为pq,请输出p×q−1 mod 109+7,此处q−1为q的逆元。
Sample Input
2
3
2 5
2 4
2 5
3
1 1
2 3
1 1
Sample Output
875000012
500000010