题目描述

音乐节奏游戏要求玩家根据旋律击打目标，在音乐进行的过程中，会依次出现 $n$ 个目标，得分与连续多少次击中有关。如果连续击中 $x$ 次，就会获得 $x^3$ 分。给定每个击打任务的击中概率，其中第 $i$ 个任务的成功概率以一个有理数 $p_i/q_i$ 表示。请计算玩家在游戏中得分的期望。

输入格式

第一行：单个正整数 $n$； 第二行到第 $n+1$ 行：第 $i+1$ 行有两个正整数 $p_i$ 与 $q_i$。

输出格式

设得分的期望为 $P/Q$，且 $P$ 和 $Q$ 互素，则输出一个整数，具体数值为

其中 $Q'Q\equiv 1\pmod {10007}$

3
1 1
1 1
1 1

27

样例解释 1

由于百分之百成功，所以分数就是3的立方

3 
1 2
1 2
1 2

6

数据范围

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