【题目描述】
记 $P = 998244353$。
你在平面直角坐标上移动。从 $(0,0)$ 出发,每一回合有 $\frac{A}{2P+1}$ 的概率向上走一格,有 $\frac{B}{2P+1}$ 的概率向右走一格,有 $\frac{2P+1-A-B}{2P+1}$ 的概率立即停止移动(之后也不再移动),三种事件两两不会同时发生;你会在第 $N$ 轮回合后离开平面直角坐标系。
已知一个常数 $D$,在所有 $xD,yD(x,y\ge 0)$ 处有一个硬币;还有 $K$ 个坑,分别在 $(x_1,y_i)\dots (x_K,y_K)$,走入坑中将在接下来的所有回合中无法行动。
你会拿走所有经过的硬币(包括 $(0,0)$),问最终期望得到的硬币数量,输出这个值
【输入格式】
第一行两个整数 $A,B$。 第二行四个整数 $N,D,M,K$。 接下来 $K$ 行,每行两个整数,第 $i+2$ 行两个数为 $x_i,y_i$。
【输出格式】
一行一个整数,表示答案。
【样例 1 输入】
1 1
2 2 5 1
1 0
【样例 1 输出】
2
【样例 1 解释】
共有 3 个地方有硬币,(0, 0),(0, 2),(2, 0)。由于 (1, 0) 处是坑,所以无法拿到 (2, 0) 处的硬币,而拿到其余两处硬币的概率均为 1。
【样例 2 输入】
1 2
2 2 5 0
【样例 2 输出】
6
【数据范围】
对于所有数据,$1\le N\le 10^{18},0\le K\le 50,1\le D,M\le 1000,0\le x_1\dots,x_K\le M,\forall i\in[1,K],D\not |x_i,D\not |y_i,x_i+y_i\le N,0\le A,B\le P-1$。
子任务 $1(9 \text{core}):n\le 10^4$
子任务 $2(12 \text{core}):n\le 10^5,D,M\le 10,K=0$
子任务 $3(27 \text{core}):K=0$
子任务 $4(8 \text{core}):n\le 10^5,D,M\le 10$
子任务 $5(44 \text{core}):$ 无特殊限制。