题目描述

本题是「CEOI2020」象棋世界，其中国王情况的加强版。

一个 $R\times C$ 的棋盘，你有 $Q$ 组询问，每次询问国王走 $R-1$ 步从 $(1,a)$ 到达 $(R,b)$ 有多少种方案。你只需要输出答案对 $998244353$ 取模的结果。

输入格式

第一行输入三个正整数 $R, C, Q$，表示棋盘的长宽以及询问次数。

接下来 $Q$ 行每行两个正整数 $a,b$，表示一组具体询问。

输出格式

输出 $Q$ 行每行一个整数，表示对应询问的方案数。

样例

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$。