Sorting Program

Time limit2sMemory limit1024 MB

Summary

Count the input sequences of N integers in [1, M] that a given list of conditional swaps sorts into ascending order, modulo 998244353.

Level: Hard8 of 10
Topics: Dynamic programming, Bit manipulation, Simulation
Solved: No attempts yet

Problem

Students in the Computer Science and Engineering department at Seoul National University take the required course 'Logic Design' in their second year. The final project for this course is an FPGA (Field Programmable Gate Array) assignment, where students implement a program that meets a given specification. This year's project is a program that takes N integers, each between 1 and $M$ inclusive, and sorts them in ascending order.

The only operation students may use is the conditional_swap operation below. Every student's program is a sequence of conditional_swap operations.

conditional_swap(x, y): If the $x$ -th integer is greater than the $y$ -th integer, swap the positions of the two integers.

Minjun, the teaching assistant lead this semester, grades the students' programs. A student's score is the number of sequences that the program sorts into ascending order. Given a student's program, help Minjun compute the score the student will receive.

Input

The first line contains $N$ , $M$ , and $K$ separated by spaces. ( $1 \le N \le 18$ ; $1 \le M \le 10^9$ ; $0 \le K \le 1000$ )

From the second line, $K$ lines each contain $x$ and $y$ separated by a space. ( $1 \le x, y \le N$ )

Output

Print the score the student receives, modulo 998244353. $998\,244\,353 = 119 \times 223 + 1$ is prime.

Examples1

Example 1
Input
```
5 2 3
2 4
3 5
1 3
```
Expected output
```
17
```