/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦横 H \times W マスの将棋盤と 2 \times H 枚の将棋の香車の駒があります。これらを用いて次のようなゲームを考えます。
ゲームは先手と後手の二人によって行われ、以下に示す手順で進行します。
- 初期状態では、先手の香車と後手の香車がすべての行に 1 枚ずつ配置されている。
- 先手から始めて先手と後手で交互に自分の駒を動かしていく。ただし相手の駒を取る(盤面から取り除く)ことはできない。
- 先に全ての自分の駒を動かせなくなった方が負けとなり、そうでない方は勝ちになる。
香車の動かせる場所は次のように定めます。ここで (i,j) を上から i 行目、左から j 列目のマスとします。
- k \lt j かつ (i,k),(i,k+1),\dots,(i,j-1) に双方の駒が存在しないとき、(i,j) にある先手の香車を (i,k) に動かすことが出来る。
- k \gt j かつ (i,j+1),(i,j+2),\dots,(i,k) に双方の駒が存在しないとき、(i,j) にある後手の香車を (i,k) に動かすことが出来る。
例えば下の図では、3\times 9 の将棋盤の (1,7),(2,1),(3,4) に先手の香車が、(1,3),(2,7),(3,5) に後手の香車が置かれています。
(1,7) の先手の香車は (1,4),(1,5),(1,6) のいずれかのマスへ、(3,4) の先手の香車は (3,1),(3,2),(3,3) のいずれかのマスへ動かすことができます。(2,1) の先手の香車は動かすことができません。
将棋を知っている人は、通常の将棋に存在する「取る」「成る」などのルールは適用されないことに注意してください。
今、将棋盤の上には何もありません。先手の香車と後手の香車を、双方の香車が同じマスに置かれないように各行に 1 枚ずつ置く方法は \left\lbrace W(W-1)\right\rbrace^H 通りあります。そのうち次の条件を満たす配置は何通りありますか？答えを 998244353 で割ったあまりを求めてください。
- その配置を初期配置としてゲームを開始して双方が最適にゲームを進めた時に先手が勝つことができる。
制約
- 1 \leq H \leq 8000
- 2 \leq W \leq 30
- H, W は整数
入力
入力は以下の形式で標準入力から与えられる。
H W
出力
答えを出力せよ。
入力例 1
1 3
出力例 1
2
先手が勝てる配置は次の 2 通りです。
- 先手の香車を (1, 3) に、後手の香車を (1, 1) に配置した場合。
- 先手の香車を (1, 2) に、後手の香車を (1, 3) に配置した場合。
入力例 2
9 9
出力例 2
583962987
入力例 3
265 30
出力例 3
366114675
Score : 600 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns, and (2 \times H) pieces. We consider the following game using them.
Two players take alternating turns. The game progresses as follows.
- In the initial state, every row contains one piece of the first player facing left and one piece of the second player facing right.
- The two players alternately advance one of their pieces.
- The player who is first to be unable to make a move loses, and the other player wins.
Let (i, j) denote the square at the i-th row from the top and j-th column from the left. The following moves are allowed:
- The first player can move a piece at (i,j) to (i,k) if k \lt j and none of (i,k),(i,k+1),\dots,(i,j-1) contains a piece of either player.
- The second player can move a piece at (i,j) to (i,k) if k \gt j and none of (i,j+1),(i,j+2),\dots,(i,k) contains a piece of either player.
For example, in the figure below, on a 3\times 9 grid, the first player's pieces are at (1,7),(2,1),(3,4), and the second player's pieces are at (1,3),(2,7),(3,5).
The first player can move the piece at (1,7) to (1,4),(1,5), or (1,6), and the piece at (3,4) to (3,1),(3,2), or (3,3). The first player cannot move the piece at (2,1).
Currently, there is no piece on the grid. There are \left\lbrace W(W-1)\right\rbrace^H ways to place one piece of the first player and one piece of the second player in each row, so that no two pieces are placed at the same square. How many of them satisfy the following condition? Find the count modulo 998244353.
- When they play the game optimally from that initial state, the first player wins.
Constraints
- 1 \leq H \leq 8000
- 2 \leq W \leq 30
- 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
1 3
Sample Output 1
2
The first player can win if:
- the first player's piece is placed at (1, 3), and the second player's piece is placed at (1, 1); or
- the first player's piece is placed at (1, 2), and the second player's piece is placed at (1, 3).
Sample Input 2
9 9
Sample Output 2
583962987
Sample Input 3
265 30
Sample Output 3
366114675