201394: [AtCoder]ARC139 E - Wazir
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