{"raw_statement":[{"iden":"background","content":"近日（存疑），一款名为闊靛緥婧愮偣的游戏更新了它的 4.0 版本。在这个版本中某谱面中的大直角蛇给玩家们留下了深刻的印象……\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/qbdvtftu.png)"},{"iden":"statement","content":"我们规定，在 $n$ 行 $m$ 列的网格中，“直角蛇”是这样一条路径：\n\n- 从最下方（第一行）的某个格子的中心开始，在最上方（第 $n$ 行）的某个格子的中心结束。\n- 每次可以向上、向右或向左移动一格，每次移动后都到达某个格子的中心（**不能向下移动**）。\n- 不能重复经过同一个格子。\n\n特别地，为了给你增加一些考验，我们规定有一些格子是“直角蛇”不能经过的。\n\n请你统计在给定的网格中存在多少种这样的“直角蛇”。答案对 $998244353$ 取模。"},{"iden":"input","content":"第一行三个整数 $n, m, q$，代表网格的行数和列数，以及限制的数量。\n\n接下来的 $q$ 行，每行两个整数 $x_i, y_i$，代表第 $x_i$ 行第 $y_i$ 列的格子不能经过。保证同一个格子至多出现一次。保证所有格子按照 $x_i$ 为第一关键字，$y_i$ 为第二关键字，从小到大排序后给出。（我们规定最下方的格子的行数为 $1$，最左侧格子的列数为 $1$）"},{"iden":"output","content":"共一行一个整数，代表符合条件的“直角蛇”数量对 $998244353$ 取模的结果。"},{"iden":"note","content":"### 数据范围\n\n**本题采用捆绑测试**。\n\n- Subtask 1（10 points）：$n \\leq 10^6$，$m \\leq 2$。\n- Subtask 2（10 points）：$q=0$。\n- Subtask 3（15 points）：$n,m \\leq 10^4$。\n- Subtask 4（20 points）：$n \\leq 10^4$。\n- Subtask 5（20 points）：$m \\leq 10^4$。\n- Subtask 6（25 points）：无特殊限制。\n\n对于所有测试数据，$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$。\n\n### 样例解释\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/dkyhh41q.png)\n\n如图，样例一中共有八种满足条件的“直角蛇”。\n\n对于样例二，不存在满足条件的“直角蛇”。\n\n---\n\n在寂若死灰中屈服。\n\n在飘忽不定中屈服。\n\n在功亏一篑中屈服。"}],"translated_statement":null,"sample_group":[["2 3 2\n1 1\n2 1","8"],["4 4 4\n1 1\n2 2\n3 3\n4 4","0"],["6 5 4\n1 3\n3 1\n3 4\n5 2","2000"],["100000000 100000000 0","103866487"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}