Дана шахматная доска размера $R\times C$. У вас есть $Q$ запросов. В каждом запросе требуется найти количество способов, которыми король может пройти из $(1,a)$ в $(R,b)$ ровно за $R-1$ ход. Выведите ответ по модулю $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
Выходные данные
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$ |