{"problem":{"name":"Teleporting Takahashi","description":{"content":"Takahashi is in the square $(0, 0, 0)$ in an infinite three-dimensional grid. He can teleport between squares. From the square $(x, y, z)$, he can move to $(x+1, y, z)$, $(x-1, y, z)$, $(x, y+1, z)$, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc240_g"},"statements":[{"statement_type":"Markdown","content":"Takahashi is in the square $(0, 0, 0)$ in an infinite three-dimensional grid.\nHe can teleport between squares. From the square $(x, y, z)$, he can move to $(x+1, y, z)$, $(x-1, y, z)$, $(x, y+1, z)$, $(x, y-1, z)$, $(x, y, z+1)$, or $(x, y, z-1)$ in one teleport. (Note that he cannot stay in the square $(x, y, z)$.)\nFind the number of routes ending in the square $(X, Y, Z)$ after exactly $N$ teleports.\nIn other words, find the number of sequences of $N+1$ triples of integers $\\big( (x_0, y_0, z_0), (x_1, y_1, z_1), (x_2, y_2, z_2), \\ldots, (x_N, y_N, z_N)\\big)$ that satisfy all three conditions below.\n\n*   $(x_0, y_0, z_0) = (0, 0, 0)$.\n*   $(x_N, y_N, z_N) = (X, Y, Z)$.\n*   $|x_i-x_{i-1}| + |y_i-y_{i-1}| + |z_i-z_{i-1}| = 1$ for each $i = 1, 2, \\ldots, N$.\n\nSince the number can be enormous, print it modulo $998244353$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^7$\n*   $-10^7 \\leq X, Y, Z \\leq 10^7$\n*   $N$, $X$, $Y$, and $Z$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $X$ $Y$ $Z$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc240_g","tags":[],"sample_group":[["3 2 0 -1","3\n\nThere are three routes ending in the square $(2, 0, -1)$ after exactly $3$ teleports:\n\n*   $(0, 0, 0) \\rightarrow (1, 0, 0) \\rightarrow (2, 0, 0) \\rightarrow(2, 0, -1)$\n*   $(0, 0, 0) \\rightarrow (1, 0, 0) \\rightarrow (1, 0, -1) \\rightarrow(2, 0, -1)$\n*   $(0, 0, 0) \\rightarrow (0, 0, -1) \\rightarrow (1, 0, -1) \\rightarrow(2, 0, -1)$"],["1 0 0 0","0\n\nNote that exactly $N$ teleports should be performed, and they do not allow him to stay in the same position."],["314 15 92 65","106580952\n\nBe sure to print the number modulo $998244353$."]],"created_at":"2026-03-03 11:01:13"}}