/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
縦 H マス、横 W マスのグリッドがあります。上から i 番目、左から j 番目のマスを (i,j) と表します。
このグリッドはトーラスであるとみなします。つまり、上下左右の 4 方向に隣り合っているマス同士に加えて、以下のマス同士も隣り合っているとみなします。
- すべての 1 \leq i \leq H を満たす整数 i について (i,1) と (i,W)
- すべての 1 \leq j \leq W を満たす整数 j について (1,j) と (H,j)
グリッドのマスにいくつかのコマを置くことを考えます。ただし各マスに置けるコマは高々 1 個であり、コマを置いたマス同士が隣り合ってはいけません。
コマを置ける個数の最大値を L とします。コマを L 個置く方法が何通りあるかを 998244353 で割ったあまりを求めてください。
制約
- 2 \leq H \leq 10^5
- 2 \leq W \leq 10^{10}
- H,W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
答えを出力せよ。
入力例 1
3 2
出力例 1
6
条件を満たす配置は次の 6 通りです。ここで、# はコマが置かれているマス、. はコマが置かれていないマスを意味します。
#. #. .# .# .. .. .# .. #. .. #. .# .. .# .. #. .# #.
入力例 2
139 424
出力例 2
148734121
入力例 3
12345 1234567890
出力例 3
227996418
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