飞机是一种非常危险的交通工具，是所有交通工具中事故存活率最低的交通工具之一。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⋅y^{-1}\bmod (10^9+7)$。可以证明 $(10^9 +7)|y$。

第一行包含一个整数 $T(1≤T≤1000)$，表示一共有 $T$ 组测试数据。

每组测试数据的第一行包含一个整数 $n(1≤n≤400)$，表示飞机的总数。

接下来 $n$ 行，每行包含 $2$ 个整数 $a_i ,b_i(2≤b_i ≤10^9 ,1≤a_i \lt b_i)$，表示第 $i$ 个飞机选择沿 $x$ 增大方向飞行的概率的分子和分母。保证 $a_i$ 与 $b_i$ 互质。

保证所有测试数据的 $n^2$ 之和不超过 $8⋅10^5$ 。

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