P9221 「TAOI-1」Pentiment

近日（存疑），一款名为闊靛緥婧愮偣的游戏更新了它的 4.0 版本。在这个版本中某谱面中的大直角蛇给玩家们留下了深刻的印象…… 

我们规定，在 $n$ 行 $m$ 列的网格中，“直角蛇”是这样一条路径： - 从最下方（第一行）的某个格子的中心开始，在最上方（第 $n$ 行）的某个格子的中心结束。 - 每次可以向上、向右或向左移动一格，每次移动后都到达某个格子的中心（**不能向下移动**）。 - 不能重复经过同一个格子。 特别地，为了给你增加一些考验，我们规定有一些格子是“直角蛇”不能经过的。 请你统计在给定的网格中存在多少种这样的“直角蛇”。答案对 $998244353$ 取模。

无

无

### 数据范围 **本题采用捆绑测试**。 - 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）：无特殊限制。 对于所有测试数据，$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$。 ### 样例解释  如图，样例一中共有八种满足条件的“直角蛇”。 对于样例二，不存在满足条件的“直角蛇”。 --- 在寂若死灰中屈服。 在飘忽不定中屈服。 在功亏一篑中屈服。