Mogu Mogu 2 Returns

• 制約違反しているケースを確認・訂正いたしました

問題文

$H$ 行 $W$ 列のグリッドがある。上から $i$ 行目 $(1 \leq i \leq H)$ 、左から $j$ 列目 $(1 \leq j \leq W)$ のマスを $(i,j)$ と呼ぶことにする。

グリッドの上におにぎりが $N$ 個置いてある。具体的には、マス $(r_1,c_1),(r_2,c_2),...,(r_N,c_N)$ の上におにぎりがそれぞれ $1$ つづつ置かれており、それ以外のマスにおにぎりは置かれていない。

お腹の空いたoさんは、マス $(1,1)$ からマス $(H,W)$ まで、右方向と下方向の移動のみを繰り返しつつ、通過したマスに置かれているおにぎりを全て食べる。ここで、このような経路として考えられる経路の集合を $S$ としたとき、 $\displaystyle \sum^{i \in S} f(i)$ の値を $mod 998244353$ で求めよ。ただし、 $f(x)$ は経路 $x$ においてoさんが食べることのできるおにぎりの数を表す。

制約

• $1 \leq H,W \leq 10^6$
• $1 \leq N \leq min(HW,2 \times 10^5)$
• $1 \leq r_i \leq H , 1 \leq c_i \leq W (1 \leq i \leq N)$
• $i \neq j$ ならば $(r_i,c_i) \neq (r_j,c_j)$

入力

入力は以下のように与えられる。

H W N
r_1 c_1
r_2 c_2
...
r_N c_N

出力

$\displaystyle \sum^{i \in S} f(i)$ の値を $998244353$ で割った余りを1行に出力せよ。

サンプル

2 2 2
1 2
2 1

2

グリッドの様子は以下のようになります。マス $(1,1)$ からマス $(H,W)$ までの経路は $(1,2)$ か $(2,1)$ のどちらかを通る $2$ 通りであり、どちらもおにぎりを $1$ つ食べることができる経路なので $1+1 = 2$ を出力します。

.#
#.

( # がおにぎりのあるマス、 . が何もないマスを表す。)

3 3 2
1 1
3 3

12

このケースにおいてはどの経路においてもおにぎりを $2$ つ食べることができるため、経路の総数が $6$ より $6 \times 2$ が答えとなります。マス $(1,1)$ やマス $(H,W)$ におにぎりが置かれていることもあります。

100000 100 7
2 1
4 2
8 4
16 8
32 16
64 32
128 64

855345322

答えを $998244353$ で割った余りを出力することに注意してください。