{"raw_statement":[{"iden":"statement","content":"Given a square grid, its lattice points labeled from $(0, 0)$ to $(n, n)$, and a number $t$.\n\nYou 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$."},{"iden":"input","content":"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$).\n\nEach 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. "},{"iden":"output","content":"For each query, output a line containing one integer, representing the answer to the query modulo $998\\,244\\,353$."},{"iden":"note","content":"**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem I.\n\n**Author**: djq_cpp."}],"translated_statement":null,"sample_group":[["2 5 3\n0 0 1 2\n1 1 2 1\n0 0 2 2\n","30\n64\n0\n"],["5 20 5\n0 0 5 5\n1 1 4 4\n2 2 3 3\n2 3 2 3\n1 2 5 2\n","615136704\n443203969\n899931333\n464755094\n679729107\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}