問題文

コアさんは恋愛アドベンチャーゲームにハマっています。

このゲームには $1, 2, \dots, N$ の番号が付いた $N$ 人のヒロインがおり、うち $M$ 人のヒロイン $1, 2, \dots, M$ はサブヒロインに分類されます。

このゲームで $N$ 人のヒロイン全員を $1$ 人 $1$ 回ずつ攻略する方法であって、
次の条件をすべて満たすものの個数を $998244353$ で割った余りを求めてください。

• ヒロイン $X_{i}$ はヒロイン $Y_{i}$ よりも先に攻略する $(1 \leq i \leq K)$

• 最初に攻略するヒロインはサブヒロインでない

制約

• $0 \leq M < N \leq 10^{6}$

• $0 \leq K \leq \min( 380, N \times (N - 1) )$

• $1 \leq X_{i}, Y_{i} \leq N$ $(1 \leq i \leq K)$

• $X_{i} \neq Y_{i}$ $(1 \leq i \leq K)$

• $(X_{i}, Y_{i}) \neq (X_{j}, Y_{j})$ $(1 \leq i < j \leq K)$

• $X_{i}, Y_{i}$ $(1 \leq i \leq K)$ として現れる整数の種類数は $20$ 以下、すなわち $\displaystyle \left| \bigcup_{i=1}^{K} \{ X_{i}, Y_{i} \} \right| \leq 20$

• 入力はすべて整数

入力

入力は次の形式で与えられます。

$N$ $M$ $K$
$X_{1}$ $Y_{1}$
$X_{2}$ $Y_{2}$
   $\vdots$
$X_{K}$ $Y_{K}$

• $1$ 行目には $N$ と $M$ と $K$ がこの順に半角スペース区切りで与えられる

• $i+1$ $(1 \leq i \leq K)$ 行目には $X_{i}$ と $Y_{i}$ がこの順に半角スペース区切りで与えられる

出力

答えを $1$ 行に出力してください。

サンプル

6 2 7
1 3
2 4
4 3
5 3
5 4
6 2
6 5

8

4 2 2
3 4
4 3

0

5 0 0

120

2015 227 10
1 200
2 310
3 420
4 530
5 640
234 6
343 696
452 501
561 711
670 821

872708262