P9366 [ICPC 2022 Xi'an R] Square Grid

Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$. You need to answer $q$ queries in this format: given $A = (x_0, y_0)$ and $B = (x_1, y_1)$, how many ways are there to move from $A$ to $B$ in exactly $t$ steps so that in each step you move from a lattice point to one of its neighbors (up, down, left, right). Calculate the answer modulo $998\,244\,353$.

The first line contains three integers $n$ ($1 \leq n \leq 10^5$), $t$ ($1 \leq t \leq 10^9$) and $q$ ($1 \leq q \leq 3 \times 10^5$). Each of the following $q$ lines contains four integers $x_0$, $y_0$, $x_1$ and $y_1$ ($0 \leq x_0, y_0, x_1, y_1 \leq n$), representing a query.

For each query, output a line containing one integer, representing the answer to the query modulo $998\,244\,353$.

**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem I. **Author**: djq_cpp.