{"problem":{"name":"[ICPC 2022 Xi'an R] Square Grid","description":{"content":"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 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":4000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9366"},"statements":[{"statement_type":"Markdown","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$.\n\n## Input\n\nThe 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. \n\n## Output\n\nFor each query, output a line containing one integer, representing the answer to the query modulo $998\\,244\\,353$.\n\n[samples]\n\n## Note\n\n**Source**: The 2022 ICPC Asia Xi'an Regional Contest Problem I.\n\n**Author**: djq_cpp.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9366","tags":["2022","O2优化","ICPC","西安"],"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"]],"created_at":"2026-03-03 11:09:25"}}