Problem Statement

Koa-san is hooked on a romance adventure game.

This game has $N$ heroines numbered $1, 2, \dots, N$, and $M$ of them, heroines $1, 2, \dots, M$, are classified as sub-heroines.

Consider the ways to complete the routes of all $N$ heroines in this game, $1$ heroine at a time and $1$ time each. Find the number of such ways,
modulo $998244353$, that satisfy all of the following conditions.

• Heroine $X_{i}$ is completed before heroine $Y_{i}$ $(1 \leq i \leq K)$

• The first heroine completed is not a sub-heroine

Constraints

• $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)$

• The number of distinct integers appearing as $X_{i}, Y_{i}$ $(1 \leq i \leq K)$ is at most $20$, that is, $\displaystyle \left| \bigcup_{i=1}^{K} \{ X_{i}, Y_{i} \} \right| \leq 20$

• All input values are integers

Input

The input is given in the following format.

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

• Line $1$ contains $N$, $M$, and $K$ in this order, separated by single-byte spaces

• Line $i+1$ $(1 \leq i \leq K)$ contains $X_{i}$ and $Y_{i}$ in this order, separated by single-byte spaces

Output

Output the answer on $1$ line.

Sample

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