12 Directions

AtCoder

IDfps_24_v

Time2000ms

Memory256MB

Difficulty—

On a 2D coordinate plane, there is a piece placed at $(0, 0)$. You will perform the following operation $N$ times: * Choose an integer $i$ such that $0 \leq i \leq 11$. If the current position of the piece is $(x, y)$, move it to $(x + \cos(30i)^\circ, y + \sin(30i)^\circ)$. Count the number of operation sequences that result in the piece being back at $(H, W)$ after $N$ operations, and output the result modulo $998244353$. ## Constraints * $1 \leq N \leq 2.5 \times 10^5$ * $-N \leq H \leq N$ * $-N \leq W \leq N$ * $N, H, W$ are integers ## Input The input is given from standard input in the following format: $N$ $H$ $W$ ## Partial Score This problem has partial scoring: * If you solve all datasets with $(H, W) = (0, 0)$, you will earn $5$ points. [samples]

Samples

Input #1

2 0 0

Output #1

12

For every integer $n$ such that $0 \leq n \leq 11$, if the first operation chooses $i = n$ and the second operation chooses $i = (n+6) \bmod 12$, the condition is satisfied. Thus, there are $12$ valid sequences.

Input #2

123456 0 0

Output #2

352845935

Input #3

50 -12 34

Output #3

391874286

Input #4

234567 89012 -34567

Output #4

523418763

API Response (JSON)

{
  "problem": {
    "name": "12 Directions",
    "description": {
      "content": "On a 2D coordinate plane, there is a piece placed at $(0, 0)$.   You will perform the following operation $N$ times: *   Choose an integer $i$ such that $0 \\leq i \\leq 11$.       If the current posit",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "fps_24_v"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "On a 2D coordinate plane, there is a piece placed at $(0, 0)$.  \nYou will perform the following operation $N$ times:\n\n*   Choose an integer $i$ such that $0 \\leq i \\leq 11$.  \n    If the current posit...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments