410696: GYM104077 I 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$$$.

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