Counting Lattice Paths in a Grid

You are given a square grid whose lattice points are labeled from \( (0,0) \) to \( (n,n) \). A positive integer \( t \) is provided. You are then given \( q \) queries. In each query, you are given two points \( A=(x_0,y_0) \) and \( B=(x_1,y_1) \). Your task is to determine the number of ways to move from \( A \) to \( B \) in exactly \( t \) steps, moving in each step to one of its four neighbors (up, down, left, right), while remaining within the grid. The answer for each query should be given modulo \( 998\,244\,353 \).

Note: You cannot move outside the grid boundaries. Each move increases or decreases exactly one coordinate by 1.

inputFormat

The first line contains three integers \( n \), \( t \), and \( q \) \( (0 \le n, t \le \text{small constraints},\; q \ge 1)\).

Each of the following \( q \) lines contains four integers \( x_0, y_0, x_1, y_1 \) representing the coordinates for points \( A \) and \( B \) respectively. It is guaranteed that \( 0 \le x_0, y_0, x_1, y_1 \le n \).

outputFormat

For each query, output a single line containing the number of ways to move from \( A \) to \( B \) in exactly \( t \) steps modulo \( 998\,244\,353 \).

sample

2 2 2
0 0 0 0
0 0 1 1

2
2