题目描述

Mashiro 菌子吃太多产生幻觉了，在幻觉中她是正在被须佐能乎命讨伐的八岐大蛇，因此她现在要赶快逃离。（接下来我们把须佐能乎命的攻击套进区间，八岐大蛇的躲闪套进求和，再加上21岁……42岁……84岁……我可能得打败你……，然后就有了一道又臭又长还不一定合理的题面……算了，懒得套了）

Mashiro 有一个长度为 \(n\) 的实数序列 \(a\)，序列的第 \(i\) 个元素 \(a_i\) 会在区间 \([l_i, r_i]\) 中随机等概率生成（在区间 \([l_i, r_i]\) 上服从均匀分布），且每个元素的生成相互独立。

Mashiro 想知道 \(\sum_{i = 2}^n |a_i - a_{i-1}|\) 的期望是多少。

定义 \(M = 10^9 + 7\)，可以证明最终的期望一定是一个有理数，也就是说答案一定可以写成 \(\frac P Q\) 的形式，因此你需要输出 \(P \times Q^{M - 2}\ mod\ M\) 的结果。

输入格式

第一行输入一个正整数 \(T(1 \le T \le 10^5)\) 表示数据组数：

对于每组数据：

第一行输入一个正整数 \(n(1 \le n \le 2 \times 10^5)\)，表示序列长度。

接下来 \(n\) 行，每行输入两个正整数 \(l, r(1 \le l \le r \le 10^9)\)，表示每一个区间。

数据保证： \(\sum n \le 10^6\)。

输出格式

对于每组数据输出一个整数表示答案。

样例输入

1
2
1 1
2 4

样例输出

2