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

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

输入格式 第一行：单个整数表示 n 第二行到第 n+1 行：第 i+1 行两个整数表示 p_i 与 q_i

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

其中 Q' 是满足 Q≡1(mod10007) 的最小正整数。

数据范围 1≤n≤2000 0≤p_i≤q_i≤10000。 样例数据 输入:

3 1 2 1 2 1 2

输出:

5004

说明: 概率为1/2 输入:

5 1 5 2 5 3 5 4 5 5 5

输出:

3267