Problem Background

Recently (allegedly), a game named "闊靛緥婧愮偣" updated to its 4.0 version. In this version, a large right-angled snake in one of the charts left a deep impression on the players...

Problem Description

We define a "right-angled snake" as a path in an $n$ by $m$ grid that:

• Starts at the center of a cell in the bottom row (row 1) and ends at the center of a cell in the top row (row $n$).
• Can move up, right, or left by one cell at a time, always ending at the center of a cell (cannot move down).
• Cannot pass through the same cell more than once.

Particularly, to add some challenge, we specify that some cells are forbidden for the "right-angled snake" to pass through.

Please count how many such "right-angled snakes" exist in the given grid. The answer should be taken modulo $998244353$.

Input Format

The first line contains three integers $n, m, q$, representing the number of rows and columns of the grid, and the number of restrictions, respectively.

The next $q$ lines each contain two integers $x_i, y_i$, indicating that the cell in the $x_i$-th row and $y_i$-th column cannot be passed through. Each cell is guaranteed to appear at most once. All cells are given sorted by $x_i$ as the primary key and $y_i$ as the secondary key, in ascending order. (We define the bottom row as row 1 and the leftmost column as column 1.)

Output Format

Output a single integer, representing the number of valid "right-angled snakes" modulo $998244353$.

Sample Input and Output

Sample Input #1

2 3 2
1 1
2 1

Sample Output #1

8

Sample Input #2

4 4 4
1 1
2 2
3 3
4 4

Sample Output #2

0

Sample Input #3

6 5 4
1 3
3 1
3 4
5 2

Sample Output #3

2000

Sample Input #4

100000000 100000000 0

Sample Output #4

103866487

Notes

Data Range

This problem uses batched testing.

• Subtask 1 (10 points): $n \leq 10^6$, $m \leq 2$.
• Subtask 2 (10 points): $q=0$.
• Subtask 3 (15 points): $n, m \leq 10^4$.
• Subtask 4 (20 points): $n \leq 10^4$.
• Subtask 5 (20 points): $m \leq 10^4$.
• Subtask 6 (25 points): No special restrictions.

For all test cases, $2 \leq n \leq 10^9$, $1 \leq m \leq 10^9$, $0 \leq q \leq 10^5$, $1 \leq x_i \leq n$, $1 \leq y_i \leq m$.

Sample Explanation

As shown in the figure, there are eight valid "right-angled snakes" in Sample 1.

For Sample 2, there are no valid "right-angled snakes".

见题面 Input 部分

见题面 Output 部分