[CoE R5] 罚球

有 $n$ 个人在玩罚球游戏，游戏规则如下： - 每个人编号为 $1,2,\dots,n$，最开始由 $1$ 号罚球，接下来让下一个没有出局的人罚球。特殊地，$n$ 号的下一个是 $1$ 号。 - 如果罚球者没有碰到篮板，那么直接出局。 - 如果罚球者碰到篮板但没有进球，那么如果上一个人进球了，这个人就会出局，否则不会出局。 - 游戏结束的条件是最后只剩下一个人。 注意最开始的那个人碰到篮板但没有进球不出局。 这 $n$ 个人中，第 $i$ 个人碰不到篮板的概率为 $\dfrac{a_i}{1000}$，碰到篮板但没有进球的概率为 $\dfrac{b_i}{1000}$，求游戏结束时所有人总共罚球数量的期望值。 ## Input 第一行两个整数 $n,t$，为人数和子任务编号。 接下来 $n$ 行，每行两个整数，为 $a_i,b_i$，保证 $0\le a_i+b_i\le1000$。 ## Output 输出一行，为所有人总共罚球数量的期望值，如果永远不会结束，那么输出 $-1$。否则，输出对 $10^6+33$ 取模的值。 [samples] ## Note **关于取模** 不会有理数取模的看[这里](https://www.luogu.com.cn/problem/P2613)。 ------------ **样例说明** 输入 $\#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$ 的倍数的情况。