连击游戏(Combo Game)

题目描述

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

输入格式

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

输出格式

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

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

样例输入 #1

3
1 1
1 1
1 1

样例输出 #1

27

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

样例输入 #2

3
1 2
1 2
1 2

样例输出 #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$。

知识点与难度

本题涉及的知识点从属于 GESP 7级，难度等级：⭐⭐⭐⭐。

测试点分布