Problem Description

There are $n$ people playing a free throw game with the following rules:
- Each person is numbered from $1$ to $n$. The game starts with player $1$ taking the shot, and then the next person who has not been eliminated takes the shot. Specifically, after player $n$, it goes back to player $1$.
- A player is immediately eliminated if they miss the backboard.
- If a player hits the backboard but fails to score, they are eliminated if the previous player scored, otherwise they remain in the game.
- The game ends when only one person remains.

Note that the first player who hits the backboard but fails to score does not get eliminated.

Among these $n$ people, the probability that the $i$-th person misses the backboard is $\dfrac{a_i}{1000}$, and the probability that they hit the backboard but fail to score is $\dfrac{b_i}{1000}$. Calculate the expected number of free throws taken by all players when the game ends.

Input Format

The first line contains two integers $n$ and $t$, representing the number of people and the subtask identifier.
The next $n$ lines each contain two integers $a_i$ and $b_i$, ensuring $0 \le a_i + b_i \le 1000$.

Output Format

Output a single line containing the expected number of free throws taken by all players. If the game never ends, output $-1$. Otherwise, output the result modulo $10^6 + 33$.

Sample Input and Output

Sample Input #1

2 8
200 400
200 400

Sample Output #1

888921

Sample Input #2

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

Sample Output #2

818968

Sample Input #3

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

Sample Output #3

315860

Sample Input #4

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

Sample Output #4

-1

Notes

Regarding Modulo Operation

For those unfamiliar with rational number modulo operations, refer to this link.

Sample Explanation

Input #1:

The probability of missing the backboard for everyone is $\dfrac{1}{5}$, and the probability of hitting the backboard but failing to score is $\dfrac{2}{5}$. The expected number of free throws is $\dfrac{25}{9}$.

Calculation (black indicates elimination, red indicates a miss without elimination, blue indicates a score):
$$\dfrac{1}{5} + \red{\dfrac{2}{5}} \times \left(\dfrac{1}{5} + \red{\dfrac{2}{5}} \times (...)) + \blue{\dfrac{2}{5}} \times (...)) = \dfrac{25}{9}$$

Input #2:

The probability of missing the backboard for everyone is $\dfrac{321}{1000}$, and the probability of hitting the backboard but failing to score is $\dfrac{637}{1000}$. The expected number of free throws is $\dfrac{1000000}{57959}$.

Data Range

This problem uses bundled testing.

Test Case 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 constant 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 properties | $17$ |

For $100\%$ of the data, $1 \le n \le 18$, $0 \le a_i, b_i, a_i + b_i \le 1000$.

Subtask 10 is scored in two parts, corresponding to $t \in \{10, 11\}$.

It is guaranteed that the denominator will never be a multiple of $10^6 + 33$.

见题面 Input 部分

见题面 Output 部分