题目描述

有 $n$ 个人在玩罚球游戏，游戏规则如下：

• 每个人编号为 $1,2,\dots,n$，最开始由 $1$ 号罚球，接下来让下一个没有出局的人罚球。特殊地，$n$ 号的下一个是 $1$ 号。
• 如果罚球者没有碰到篮板，那么直接出局。
• 如果罚球者碰到篮板但没有进球，那么如果上一个人进球了，这个人就会出局，否则不会出局。
• 游戏结束的条件是最后只剩下一个人。

注意最开始的那个人碰到篮板但没有进球不出局。

这 $n$ 个人中，第 $i$ 个人碰不到篮板的概率为 $\dfrac{a_i}{1000}$，碰到篮板但没有进球的概率为 $\dfrac{b_i}{1000}$，求游戏结束时所有人总共罚球数量的期望值。

输入格式

第一行两个整数 $n,t$，为人数和子任务编号。
接下来 $n$ 行，每行两个整数，为 $a_i,b_i$，保证 $0\le a_i+b_i\le1000$。

输出格式

输出一行，为所有人总共罚球数量的期望值，如果永远不会结束，那么输出 $-1$。否则，输出对 $10^6+33$ 取模的值。

2 8
200 400
200 400

888921

7 8
321 637
321 637
321 637
321 637
321 637
321 637
321 637

818968

6 10
338 270
229 413
132 133
141 173
157 686
616 250

315860

8 10
338 270
229 413
132 133
141 173
157 686
616 250
0 0
0 0

-1

提示

关于取模

不会有理数取模的看这里。

---

样例说明

输入 $\#1$：

所有人碰不到篮板的概率都是 $\dfrac{1}{5}$，碰到篮板但不进球的概率都是 $\dfrac{2}{5}$，罚球数量的期望值为 $\dfrac{25}{9}$。

计算如下（黑色表示出局，红色表示没进球但不出局，蓝色表示进球）：

$$\dfrac{1}{5}+\red{\dfrac{2}{5}}\times(\dfrac{1}{5}+\red{\dfrac{2}{5}}\times(...)+\blue{\dfrac{2}{5}}\times(...))+\blue{\dfrac{2}{5}}\times(\dfrac{3}{5}+\blue{\dfrac{2}{5}}\times(...))=\dfrac{25}{9} $$

输入 $\#2$：

所有人碰不到篮板的概率都是 $\dfrac{321}{1000}$，碰到篮板但不进球的概率都是 $\dfrac{637}{1000}$，罚球数量的期望值为 $\dfrac{1000000}{57959}$。

---

数据范围

本题采用捆绑测试。

测试点性质： | $t=$ | 性质 | 分数 | | :----------: | :----------: | :----------: | | $1$ | $n=1$ | $2$ | | $2$ | $a_i=b_i=0$ | $2$ | | $3$ | $a_i=1000$ | $4$ | | $4$ | $b_i=1000$ | $4$ | | $5$ | $a_i=0,b_1=0,\forall i>1,b_i=1000$ | $6$ | | $6$ | $a_i=b_i=500$ | $6$ | | $7$ | $a_i=0,b_i=500$ | $6$ | | $8$ | $a_i,b_i$ 均为定值，且答案不为 $-1$ | $19$ | | $9$ | $1 \le n \le 11$ | $26$ | | $10$ | $1 \le n \le 15$ | $8$ | | $11$ | 无特殊性质 | $17$ |

对于 $100\%$ 的数据，$1 \le n \le 18$，$0 \le a_i,b_i,a_i+b_i \le 1000$。

本题的 $\text{Subtask 10}$ 分为两部分计分，对应 $t \in \{10,11\}$。

保证不存在分母为 $10^6+33$ 的倍数的情况。