Description

给定一个方形网格，其格点标记从 $(0, 0)$ 到 $(n, n)$，以及一个数字 $t$。

你需要回答 $q$ 个查询，每个查询的格式为：给定 $A = (x_0, y_0)$ 和 $B = (x_1, y_1)$，有多少种方法可以在恰好 $t$ 步内从 $A$ 移动到 $B$，使得每一步都从一个格点移动到其相邻的格点（上、下、左、右）。计算答案对 $998\,244\,353$ 取模。

Input Format

第一行包含三个整数 $n$ ($1 \leq n \leq 10^5$)，$t$ ($1 \leq t \leq 10^9$) 和 $q$ ($1 \leq q \leq 3 \times 10^5$)。

接下来的 $q$ 行中的每一行包含四个整数 $x_0$，$y_0$，$x_1$ 和 $y_1$ ($0 \leq x_0, y_0, x_1, y_1 \leq n$)，表示一个查询。

Output Format

对于每个查询，输出一行包含一个整数，表示该查询的答案对 $998\,244\,353$ 取模。

2 5 3
0 0 1 2
1 1 2 1
0 0 2 2

30
64
0

5 20 5
0 0 5 5
1 1 4 4
2 2 3 3
2 3 2 3
1 2 5 2

615136704
443203969
899931333
464755094
679729107

Hint

来源：2022 年 ICPC 亚洲西安区域赛问题 I。

作者：djq_cpp。

题面翻译由 ChatGPT-4o 提供。