Background

Recently (dubious), a game called 闊靛緥婧愮偣 updated to version 4.0. In this version, a certain chart’s huge right-angle snake left a deep impression on the players...

Problem Description

We define the following in an $n$-row, $m$-column grid: a “right-angle snake” is a path with these rules:

• It starts from the center of some cell in the bottommost row (row $1$) and ends at the center of some cell in the topmost row (row $n$).
• Each move can go up, right, or left by one cell, and after each move it arrives at the center of a cell (moving down is not allowed).
• It cannot pass through the same cell more than once.

In particular, to make it more challenging, some cells are forbidden for the “right-angle snake” to pass through.

Count how many such “right-angle snakes” exist in the given grid. Output the answer modulo $998244353$.

Input Format

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

The next $q$ lines each contain two integers $x_i, y_i$, meaning that the cell at row $x_i$ and column $y_i$ cannot be passed through. It is guaranteed that each cell appears at most once. It is guaranteed that all cells are given in increasing order when sorted by $x_i$ as the primary key and $y_i$ as the secondary key. (We define the bottommost row as row $1$, and the leftmost column as column $1$.)

Output Format

Output one integer: the number of valid “right-angle snakes” modulo $998244353$.

2 3 2
1 1
2 1

8

4 4 4
1 1
2 2
3 3
4 4

0

6 5 4
1 3
3 1
3 4
5 2

2000

100000000 100000000 0

103866487

Hint

Constraints

This problem uses bundled testdata.

• 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 testdata, $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-angle snakes” in Sample 1.

For Sample 2, there are no valid “right-angle snakes”.

Surrender in ashes as cold as death.

Surrender amid drifting uncertainty.

Surrender at the last step, just short of success.

Translated by ChatGPT 5