P9221 "TAOI-1" Pentiment

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... 

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$.

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 one integer: the number of valid “right-angle snakes” modulo $998244353$.

### 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