$R\times C$ のチェス盤がある。$Q$ 個のクエリが与えられる。各クエリでは、キングが $(1,a)$ から $(R,b)$ まで $R-1$ 手で移動する方法が何通りあるかを求める。答えを $998244353$ で割った余りを出力せよ。
入力
1行目に3つの正整数 $R, C, Q$ が与えられる。これらはチェス盤の縦横のサイズとクエリの回数を表す。
続く $Q$ 行の各行には、2つの正整数 $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
小課題
すべてのデータにおいて、$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$ |