题目描述

有 $n$ 枚硬币，其中第 $i$ 枚硬币有 $\frac{p_i}{q_i}$ 的概率扔出正面（其余概率出现反面）， 这些硬币扔完后，正面硬币数量超过反面硬币数量的概率是多少？

正面硬币数与反面硬币数相等不算超过。

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行两个整数表示 $p_i$ 与 $q_i$

输出格式

设最终概率为 $P/Q$，且 $P$ 和 $Q$ 互素，则输出一个整数，具体数值为

其中 $Q'$ 是满足 $Q'Q\equiv 1\pmod {10007}$ 的最小正整数。

3
1 2
1 2
1 2

5004

样例解释 1

概率为1/2

5
1 5
2 5
3 5
4 5
5 5

3267

数据范围

• 对于 $30\%$ 的数据，$1\leq n\leq 10$；
• 对于 $60\%$ 的数据，$1\leq n\leq 200$；
• 对于 $100\%$ 的数据，$1\leq n\leq 2000$
• $0\leq p_i\leq q_i\leq 10000$。