生产机器

Problem Description

某型号的作业机器人可以生产蓝色和黄色两种充能球。根据接下来 $n$ 小时的工作计划，该机器人在第 $i$ 小时可以生产至多 $l_i$ 个黄色充能球和 $f_i$ 个蓝色充能球，也可以不生产任何一个充能球。 在接下来 $n$ 个小时的工作结束之后，该机器人生产的充能球将按其被生产的顺序依次装入集装箱。具体而言，每小时内生产的充能球的顺序可以由机器人任意确定，而前一小时生产的所有充能球都排在后一小时生产的充能球之前。 现在，请你计算，最终集装箱中装入的充能球所构成的序列共有多少种可能。两个序列不同当且仅当其包含的充能球总数不同，或者存在一个 $i$，使得两个序列中生产的第 $i$ 个充能球颜色不同。由于答案可能很大，你只需要输出答案对 $10^9 + 7$ 取模的结果。

Input

第一行一个整数 $t$ $(1 \leq t \leq 1000)$，表示测试数据的组数。 对于每组测试数据： 第一行一个整数 $n$ $(1 \leq n \leq 10^5)$，表明机器人的工作时长。 接下来 $n$ 行，每行两个整数 $l_i$ 和 $f_i$ $(0 \leq l_i, f_i \leq 10^6)$，表明该机器人第 $i$ 小时最多可以生产的两种充能球的个数。 保证对于所有数据的 $\sum n \leq 2 \times 10^6$。

Output

对于每组数据输出一行一个整数，表明所求的答案。

Sample Input

2
1
0 3
2
2 3
4 1

Sample Output

4
389

Source

2024“钉耙编程”中国大学生算法设计超级联赛（7）