4556. KR-976

单点时限: 2.0 sec

内存限制: 512 MB

KR-976 loves mahjong, but it is especially hard to level up in maj-soul, so she begin to think when she will level up.

Now KR-976 simplifies and formalizes the problem and wants you to solve it:

In such a game, the player has $S$ points initially, and if her point may reach $T$,she will level up. Now she have $n$ rounds of the game to play. Each round may cause $m$ results. The $i$-th result will happen with probability $p_i$ and lead to $c_i$ points change.

Moreover, during the $n$ rounds:

  • If the player’s current points is less than or equal to 0, the player fails to level-up and can’t continue the rest rounds.

  • If the player’s current points is greater than or equal to $T$, the player will level up immediately and skip the rest games.

Now, your task is help the player to find the probability of level-up after at most $n$ rounds.

It is guaranteed the answer may be written by $p/q$, where $p,q$ are integers. To avoid precision of floating number, you should output an integer $x$ such as $0\le x<998244353, qx\equiv p\pmod {998244353}$.

输入格式

The first line contains four integers $S、T、n、m$, representing the initial points, the aim points, the number of games and the number of results for each game respectively.

The next $m$ lines, each line contains two integers. The $(i+1)$-th line has two integers $w_i、c_i$, where $p_i=w_i/10000$ represents the probability of the $i$-th result and $c_i$ means the change of points.

输出格式

Output a line, which contains an integer $p$.

样例

Input
10 20 1 2
5000 10
5000 -10
Output
499122177
Input
10 30 2 3
3000 50
3000 10
4000 -10
Output
838525257

提示

$0<S<T\leq 10000$

$0 < n \leq 10000,0 < m \leq 10$

$0< w_i\leq 10000, \sum w_i=10000$

$-10000\leq c_i\leq 10000,\gcd(c_1,…,c_m)\geq 10$

Where $\gcd$ means the greatest common divisor .

Sample 1 Explanation:

There is only one round.

The initial points is $10$.

The points needed to level up is $20$.

The player has 0.5 probability to make the point increase by $10$ (10+10=20, level-up!) and 0.5 probability to make it decrease by $10$ (10-10=0, failure!). So the answer is 0.5 , which is $499122177$ modulo $998244353$.

Sample 2 Explanation:

the probability is $0.3 + 0.3 * (0.3 + 0.3) = 0.48$

25 人解决,29 人已尝试。

35 份提交通过,共有 173 份提交。

4.6 EMB 奖励。

创建: 1 月前.

修改: 1 月前.

最后提交: 2 周,1 天前.

来源: N/A

题目标签