P8580 [CoE R5] Free Throws

There are $n$ people playing a free throw game. The rules are as follows: - Each person is numbered $1,2,\dots,n$. At the beginning, player $1$ takes a free throw. After that, the next player who has not been eliminated takes a free throw. In particular, after player $n$ comes player $1$. - If the shooter does not hit the backboard, they are eliminated immediately. - If the shooter hits the backboard but does not score, then if the previous player scored, this shooter will be eliminated; otherwise, they will not be eliminated. - The game ends when there is only one person left. Note that the first player will not be eliminated if they hit the backboard but do not score. Among these $n$ people, for player $i$, the probability of not hitting the backboard is $\dfrac{a_i}{1000}$, and the probability of hitting the backboard but not scoring is $\dfrac{b_i}{1000}$. Find the expected total number of free throws taken by all players when the game ends.

The first line contains two integers $n,t$, representing the number of players and the subtask index. The next $n$ lines each contain two integers $a_i,b_i$, and it is guaranteed that $0\le a_i+b_i\le1000$.

Output one line: the expected total number of free throws taken by all players. If the game will never end, output $-1$. Otherwise, output the value modulo $10^6+33$.

**About modulo** If you do not know how to take modulo of rational numbers, see [here](https://www.luogu.com.cn/problem/P2613). ------------ **Sample Explanation** Input $\#1$: For everyone, the probability of not hitting the backboard is $\dfrac{1}{5}$, and the probability of hitting the backboard but not scoring is $\dfrac{2}{5}$. The expected number of free throws is $\dfrac{25}{9}$. The calculation is as follows (black means eliminated, red means no score but not eliminated, blue means scored): $$\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}$$ Input $\#2$: For everyone, the probability of not hitting the backboard is $\dfrac{321}{1000}$, and the probability of hitting the backboard but not scoring is $\dfrac{637}{1000}$. The expected number of free throws is $\dfrac{1000000}{57959}$. ------------ **Constraints** **This problem uses bundled tests**. Test point properties: | $t=$ | Property | Score | | :----------: | :----------: | :----------: | | $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$ are both fixed values, and the answer is not $-1$ | $19$ | | $9$ | $1 \le n \le 11$ | $26$ | | $10$ | $1 \le n \le 15$ | $8$ | | $11$ | No special property | $17$ | For $100\%$ of the testdata, $1 \le n \le 18$, $0 \le a_i,b_i,a_i+b_i \le 1000$. Subtask $10$ of this problem is scored in two parts, corresponding to $t \in \{10,11\}$. It is guaranteed that there is no case where the denominator is a multiple of $10^6+33$. Translated by ChatGPT 5