有一個 $R\times C$ 的棋盤，你有 $Q$ 組詢問，每次詢問國王走 $R-1$ 步從 $(1,a)$ 到達 $(R,b)$ 有多少種方案。你只需要輸出答案對 $998244353$ 取模的結果。
輸入格式
第一行輸入三個正整數 $R, C, Q$，表示棋盤的長寬以及詢問次數。
接下來 $Q$ 行每行兩個正整數 $a,b$，表示一組具體詢問。
輸出格式
輸出 $Q$ 行每行一個整數，表示對應詢問的方案數。
範例
範例 1 輸入
13 10 10 10 1 2 2 9 1 10 5 8 8 9 1 9 3 7 5 5 6 8 10
範例 1 輸出
328 45475 1142 12804 65715 1142 7995 58199 69552 29964
子任務
對於 $100\%$ 的資料，保證 $2\le C\le 10^5, C\le R\le 10^9, 1\le Q\le 10^5$。
| 子任務編號 | $C\le$ | $Q\le $ | 分值 |
|---|---|---|---|
| $1$ | $10^2$ | $10^4$ | $11$ |
| $2$ | $10^3$ | $10$ | $14$ |
| $3$ | $10^5$ | $25$ | |
| $4$ | $10^5$ | $10^2$ | $30$ |
| $5$ | $10^5$ | $20$ |