Dana jest szachownica o wymiarach $R\times C$ oraz $Q$ zapytań. W każdym zapytaniu należy obliczyć, na ile sposobów król może przejść z pola $(1,a)$ na pole $(R,b)$, wykonując dokładnie $R-1$ ruchów. Wynik należy podać modulo $998244353$.
Wejście
W pierwszej linii znajdują się trzy liczby całkowite dodatnie $R, C, Q$, oznaczające odpowiednio wysokość szachownicy, szerokość szachownicy oraz liczbę zapytań.
W kolejnych $Q$ liniach znajdują się po dwie liczby całkowite dodatnie $a, b$, opisujące poszczególne zapytania.
Wyjście
Dla każdego zapytania wypisz w osobnej linii liczbę sposobów przejścia modulo $998244353$.
Przykład
Przykład 1
Wejście
13 10 10 10 1 2 2 9 1 10 5 8 8 9 1 9 3 7 5 5 6 8 10
Wyjście
328 45475 1142 12804 65715 1142 7995 58199 69552 29964
Podzadania
Dla $100\%$ danych wejściowych spełnione są warunki: $2\le C\le 10^5, C\le R\le 10^9, 1\le Q\le 10^5$.
| Numer podzadania | $C\le$ | $Q\le $ | Punkty |
|---|---|---|---|
| $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$ |