Problem Description

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.

Input Format

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 Format

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$.

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

Hint

About modulo

If you do not know how to take modulo of rational numbers, see here.

---

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