Walk Alone is playing a game recently. In this game, there are monsters numbered from to , the -th of which has an attack ability of . Walk Alone is required to kill all of them in order.

To kill a monster, he needs to battle with it. He can battle with the -th monster if and only if all monsters from to are killed.

• , he kills the monster.
• , he kills the monster, but his attack ability may become with a probability of .
• , he loses the battle. The monster is still alive, but his attack ability may become with a probability of .

When he loses a battle, he will keep trying until he wins.

Now Walk Alone wants to know the \textbf{expected number of battles} he needs to go through in total.

It can be shown that the answer can always be expressed as an irreducible fraction , where and are integers and . Output such an integer that and .

The first line contains an integer , the number of monsters.

The -th of the next  lines contains two integers  and , and .

Output a single number, the expected number of battles modulo .

3
1 100
0 50
1 100

499122181

In the first example, the result of each battle is as below:
  - Battle 1: monster  is still alive, and his attack ability become .
  - Battle 2: monster  is killed, and his attack ability remains .
  - Battle 3: monster  is killed, and with  probability his attack ability become .
  - If his attack ability is :
    - Battle 4: monster  is still alive, and his attack ability become .
    - Battle 5: monster  is killed.
  - If his attack ability is , monster  is killed in battle .

The expected number of battles is , which is congruent to  modulo .

5
2 50
6 30
1 20
5 50
4 40

332748140