410191: GYM103973 A Monster Killer

Walk Alone is playing a game recently. In this game, there are $$$n$$$ monsters numbered from $$$1$$$ to $$$n$$$, the $$$i$$$-th of which has an attack ability of $$$a_i$$$. 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 $$$(i+1)$$$-th monster if and only if all monsters from $$$1$$$ to $$$i$$$ are killed.

Initially, Walk Alone's attack ability $$$m$$$ equals to $$$0$$$. After a battle with the $$$i$$$-th monster, three situations may happen:

• $$$m = a_i$$$, he kills the monster.
• $$$m > a_i$$$, he kills the monster, but his attack ability $$$m$$$ may become $$$m - 1$$$ with a probability of $$$p_i$$$.
• $$$m < a_i$$$, he loses the battle. The monster is still alive, but his attack ability $$$m$$$ may become $$$m + 1$$$ with a probability of $$$p_i$$$.

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

Now Walk Alone wants to know the 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 $$$x/y$$$, where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0 \pmod{998\,244\,353}$$$. Output such an integer $$$a$$$ that $$$0 \leq a < 998\,244\,353$$$ and $$$a\cdot y \equiv x \pmod{998\,244\,353}$$$.

The first line contains an integer $$$n\ (1 \leq n \leq 10^3)$$$, the number of monsters.

The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$a_i\ (0 \leq a_i \leq 10^3)$$$ and $$$x_i\ (1 \leq x_i \leq 100 )$$$, and $$$p_{i} = 0.01\,x_i$$$.

Output a single number, the expected number of battles modulo $$$998\,244\,353$$$.

3
1 100
0 50
1 100

499122181

5
2 50
6 30
1 20
5 50
4 40

332748140

In the first example, the result of each battle is as below:

• Battle 1: monster $$$1$$$ is still alive, and his attack ability become $$$1$$$.
• Battle 2: monster $$$1$$$ is killed, and his attack ability remains $$$1$$$.
• Battle 3: monster $$$2$$$ is killed, and with $$$50\%$$$ probability his attack ability become $$$0$$$.
• If his attack ability is $$$0$$$:
  • Battle 4: monster $$$3$$$ is still alive, and his attack ability become $$$1$$$.
  • Battle 5: monster $$$3$$$ is killed.
  If his attack ability is $$$1$$$, monster $$$3$$$ is killed in battle $$$4$$$.

The expected number of battles is $$$4.5$$$, which is congruent to $$$499\,122\,181$$$ modulo $$$998\,244\,353$$$.