cats 的飞机坠毁

Problem Description

飞机是一种非常危险的交通工具，是所有交通工具中事故存活率最低的交通工具之一。cats 对乘坐飞机感到非常恐惧。 在一个数轴上有 $n$ 个编号从 $1$ 到 $n$ 的飞机，其中编号为 $i$ 的飞机初始位于数轴上 $x=i$ 的位置。然后，每个飞机将会相互独立的随机选择自己的飞行方向。其中第 $i$ 个飞机有 $\frac{a_i}{b_i}$ 的概率选择沿 $x$ 增大方向飞行，有 $1-\frac{a_i}{b_i}$ 的概率选择沿 $x$ 减小方向飞行。所有飞机飞行的速率均为每秒 $1$ 个单位长度，且都在第 $0$ 秒开始时开始飞行。在飞行过程中，如果在任意时刻的任意坐标位置（包括非整数坐标）存在超过 $1$ 个飞机，就会发生一次飞机坠毁。所有处在这一坐标上的飞机都会坠毁并消失(不再参与后续的飞机坠毁)。 现在，cats 想知道最后一次飞机坠毁发生的时间(按秒计算)的数学期望对 $10^9+7$ 取模的结果。如果没有任何飞机坠毁发生，则认为最后一次飞机坠毁发生的时间为 $0$。 可以证明答案一定可以被表示为一个有理数 $\frac{x}{y}$。其中 $x$ 与 $y$ 互质。你需要输出 $x \cdot y^{-1} \bmod (10^9+7)$。可以证明 $(10^9+7) \nmid y$。

Input

第一行包含一个整数 $T$ $(1\leq T \leq 1000)$，表示一共有 $T$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$ $(1\leq n\leq 400)$，表示飞机的总数。 接下来 $n$ 行，每行包含 $2$ 个整数 $a_i,b_i$ $(2 \leq b_i \leq 10^9,1 \leq a_i < b_i)$，表示第 $i$ 个飞机选择沿 $x$ 增大方向飞行的概率的分子和分母。保证 $a_i$ 与 $b_i$ 互质。 保证所有测试数据的 $n^2$ 之和不超过 $8\cdot 10^5$。

Output

对于每组测试数据，输出一个整数，表示最后一次飞机坠毁发生的时间(按秒计算)的数学期望对 $10^9+7$ 取模的结果。

Sample Input

4
1
13 37
2
1 2
1 2
3
1 2
1 3
2 3
7
405082616 465273293
75486143 274603790
335370224 859624599
367950901 497839321
185066160 809056603
277437177 572935355
274625651 316202992

Sample Output

0
125000001
222222224
352222809

Source

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