201394: [AtCoder]ARC139 E - Wazir

Memory Limit:1024 MB Time Limit:10 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $800$ points

Problem Statement

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$

Output

Print the answer.


Sample Input 1

3 2

Sample Output 1

6

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

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

Sample Input 2

139 424

Sample Output 2

148734121

Sample Input 3

12345 1234567890

Sample Output 3

227996418

Input

加入题单

上一题 下一题 算法标签: