Given an $R\times C$ chessboard, you have $Q$ queries. For each query, determine the number of ways a king can travel from $(1, a)$ to $(R, b)$ in exactly $R-1$ steps. Output the answer modulo $998244353$.
Input
The first line contains three positive integers $R, C, Q$, representing the dimensions of the chessboard and the number of queries.
Each of the next $Q$ lines contains two positive integers $a$ and $b$, representing a specific query.
Output
Output $Q$ lines, each containing an integer representing the number of ways for the corresponding query.
Examples
Input 1
13 10 10 10 1 2 2 9 1 10 5 8 8 9 1 9 3 7 5 5 6 8 10
Output 1
328 45475 1142 12804 65715 1142 7995 58199 69552 29964
Subtasks
For $100\%$ of the data, it is guaranteed that $2\le C\le 10^5$, $C\le R\le 10^9$, and $1\le Q\le 10^5$.
| Subtask ID | $C\le$ | $Q\le $ | Score |
|---|---|---|---|
| $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$ |