555 「LibreOJ Round #8」Moejy0viiiiiv's Red Envelopes

Moejy0viiiiiv is collecting red envelopes on a rectangular plane. She starts at $(0,0)$. Every day at noon, she walks from $(x, y)$ to $(x,y+1)$ with probability $A/1996488707$, and to $(x+1,y)$ with probability $B/1996488707$, and stops immediately with probability $1-A/1996488707-B/1996488707$ (once she stops, she will never move again). Besides, she also stops after walking for $N$ days.

With a given constant integer $D$, there’s a red envelope at each $(xD, yD)(0 \leq x, y)$. There’re also $K$ barriers at $(x_1, y_1), (x_2, y_2), (x_3, y_3), ..., (x_K, y_K)$ (barriers never coincide with red envelopes). If she walks to a barrier, she will stop immediately.

Moejy0viiiiiv will collect each red envelope she passes by (including $(0,0)$). What’s the expected number of red envelopes Moejy0viiiiiv collects after $N$ days? Output the answer $\bmod 998244353$. Notice that $1996488707 \bmod 998244353 = 1$.

The first line contains two positive integers $A,B$.

The second line contains four positive integers $N,D,M,K$.

The following $K$ lines each contains two integers, the $i+2$-th line contains $x_i,y_i$.

Output contains one integer, the expected number of red envelopes $\bmod 998244353$.

There’re three red envelopes satisfies $x+y\le N$, $(0, 0), (0, 2), (2, 0)$. As there’s a barrier at $(1, 0)$, the red envelope at $(2, 0)$ is unreachable. The probability of getting the other two red envelopes are both $1$.

$A+B$ doesn’t need to be $1$.

For all test cases, $1 \leq N \leq 10^{18}, 0 \leq K \leq 50, 1 \leq D, M \leq 1000, 0 \leq x_1, x_2, ..., x_K \leq M$, $\forall i \in {1, 2, 3, ..., K}, D \nmid x_i \vee D \nmid y_i, x_i + y_i \leq N, 0 \leq A, B < 998244353$.

Detailed constraints are as follows (blank grids denote the same constraints as mentioned above):