P9366 [ICPC 2022 Xi'an R] Square Grid

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

第一行包含三个整数 $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$)，表示一个查询。

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

**来源**：2022 年 ICPC 亚洲西安区域赛问题 I。 **作者**：djq_cpp。 题面翻译由 ChatGPT-4o 提供。