Wazir

AtCoder

IDarc139_e

Time10000ms

Memory256MB

Difficulty—

We have a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$\-th row from the top and $j$\-th column from the left. Assume that this grid is a torus; that is, in addition to the pairs of squares horizontally or vertically adjacent to each other, assume the following pairs of squares to be adjacent to each other. * $(i,1)$ and $(i,W)$, for every integer $i$ such that $1 \leq i \leq H$. * $(1,j)$ and $(H,j)$, for every integer $j$ such that $1 \leq j \leq W$. Consider placing some number of pieces on the squares in the grid. Here, there can be at most one piece on each square, and there cannot be two pieces on adjacent squares. Let $L$ be the maximum number of pieces that can be placed. Find the number of ways, modulo $998244353$, to place $L$ pieces. ## Constraints * $2 \leq H \leq 10^5$ * $2 \leq W \leq 10^{10}$ * $H$ and $W$ are integers. ## Input Input is given from Standard Input in the following format: $H$ $W$ [samples]

Samples

Input #1

3 2

Output #1

6

The following six placements satisfy the condition. Here, `#` and `.` represent a square with and without a piece, respectively.

#.   #.   .#   .#   ..   ..
.#   ..   #.   ..   #.   .#
..   .#   ..   #.   .#   #.

Input #2

139 424

Output #2

148734121

Input #3

12345 1234567890

Output #3

227996418

API Response (JSON)

{
  "problem": {
    "name": "Wazir",
    "description": {
      "content": "We have a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.   Assume that this grid is a torus; that is, in addition ",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 10000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "arc139_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "We have a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.  \nAssume that this grid is a torus; that is, in addition ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments