Problem Description

"看似随机，实则早已注定"——光羽

度度熊有$n$个随机变量$x_1,x_2,...,x_n$。给定区间$[l_1, r_1],...,[l_n, r_n]$，变量$x_i$的值会**等概率**成为区间$[l_i, r_i]$中的任意一个**整数**。

显然这$n$个随机变量的值会有一共$\prod_{i=1}^{n} (r_i - l_i + 1) $ 种情况，且每种情况出现的概率为$\prod_{i=1}^{n} \frac{1}{r_i - l_i + 1}$ 。

对于某种情况，令$h= \max\{ x_1,x_2,...,x_n\}$，定义这种情况的**权值**为：$\prod_{i=1}^{n} (h - x_i + 1)$.

度度熊想知道权值的**期望**是多少？请将答案对$10^9 + 7$取模后输出。

PS：不清楚期望是啥？为什么不问问神奇的百度呢？

Input

第一行一个数，表示数据组数$T$。

每组数据第一行一个整数$n$；接下来$n$行，每行两个数，表示$l_i$和$r_i$。

数据组数T=100，满足：

- $1 \le n \le 100$
- $1 \le l_i \le r_i \le 10^4$

其中70%的数据满足$r_i \le 100$。

Output

每组数据输出一行，每行仅包含一个数，表示期望。

假设答案为$\frac{p}{q}$，请输出$p \times q^{-1} ~mod~10^9+7$，此处$q^{-1}$为$q$的逆元。

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

875000012
500000010

Hint

第二组数据的解释：序列只有两种情况（1,2,1）和(1,3,1)，权值分别为2*1*2=4和3*1*3=9，答案为(4+9)/2，在模域下为500000010。