問題文

$H$ 行 $W$ 列のマス目があり，$i$ 行 $j$ 列目のマスをマス $(i,j)$ と表します．最初，あなたはマス $(1,1)$ にいます．

あなたは，マス $(i,j)$ からマス $(i+1,j)$ またはマス $(i,j+1)$ へ移動することを繰り返してマス $(H,W)$ を目指します．ただし，マス目の外に出るような移動はできません．

このマス目の中の $N$ マスには良い知らせが言い伝えられており，$k$ 番目の良い知らせはマス $(x_k, y_k)$ に言い伝えられています．

さて，マス $(1,1)$ およびマス $(H,W)$ を除くすべてのマスでは，一定の確率で白い蓮の花が咲きます．各マスに白い蓮の花が咲く確率は，そのマスに良い知らせが言い伝えられている場合 $\frac{2}{P}$，そうでない場合 $\frac{1}{P}$ です（白い蓮の花が咲くかどうかはマスごとに独立に決まります）．白い蓮の花を見ることができるのは，白い蓮の花が咲いているマスと同じマスにいるときのみです．また，今いるマス以外のマスに白い蓮の花が咲いているかどうかを知ることはできません．

あなたは，マス $(1,1)$ からマス $(H,W)$ に移動するまでに一度でも白い蓮の花を見られる確率を最大化したいです．確率が最大となる移動方法を取った場合に，白い蓮の花を見ることができる確率を，以下の注記に示すように$\bmod 998244353$ で求めてください．

注記

求める値は有理数となることが証明できます．また，この問題の制約下では，その値を互いに素な $2$ つの正整数 $X,Y$ を用いて $\frac{Y}{X}$ と表したとき，$XZ \equiv Y \pmod{998244353}$ となる整数 $Z$ が $0 \leq Z < 998244353$ の範囲にただ一つ存在することが証明できます．この $Z$ を出力してください．

制約

• 入力は全て整数である．
• $2 \leq H,W \leq 2 \times 10^5$
• $0 \leq N \leq \min(HW - 2, 2 \times 10^5)$
• $2 \leq P < 998244353$
• $1 \leq x_k \leq H$
• $1 \leq y_k \leq W$
• $(x_k, y_k) \neq (1,1)$
• $(x_k, y_k) \neq (H,W)$
• $(x_k, y_k) \neq (x_l, y_l) (k \neq l)$

入力

入力は以下の形式で標準入力から与えられる．

$H$ $W$ $N$ $P$
$x_1$ $y_1$
$x_2$ $y_2$
$\vdots$
$x_N$ $y_N$

出力

一度でも白い蓮の花を見ることができる確率を，注記に示すように $\bmod 998244353$ で出力せよ．

サンプル

3 4 3 3
1 2
2 1
3 3

690144245

2 2 1 2
1 2

1

12 15 8 2009
1 4
3 1
2 4
2 5
5 2
7 3
9 3
11 14

438033477