No.2802 Pill Bug in Grid Maze
Problem Statement
Pill bugs live in the Yukicoder region.
Consider moving a pill bug on an $H \times W$ grid.
The cell in the $i$-th row from the top and the $j$-th column from the left is denoted by cell $(i, j)$.
All cells outside the $H \times W$ range are treated as having obstacles.
- If the cell adjacent in the direction it is facing has no obstacle, it moves to that cell.
- When it bumps into an obstacle for an odd-numbered time, it rotates its facing direction $90°$ to the right.
- When it bumps into an obstacle for an even-numbered time, it rotates its facing direction $90°$ to the left.
More strictly, "bumping into an obstacle" means that an obstacle is placed on the cell adjacent in the direction it is facing.
Now, consider creating a maze by choosing $0$ or more cells of the grid and placing an obstacle on each chosen cell.
There are $2^{HW}$ different mazes that can be generated. How many of them satisfy the following conditions?
- No obstacles are placed on cell $(1, 1)$ and cell $(H, W)$.
- Initially, the pill bug is placed on cell $(1, 1)$ facing right. Then, the pill bug can reach cell $(H, W)$ through a finite number of actions.
Since the answer can be very large, find it modulo $998244353$.
Constraints
- $H, W$ are integers
- $1 \leq H, W \leq 2 \times 10^5$
Input
The input is given from standard input in the following format.
$H\ W$
Output
Output the number of mazes satisfying the conditions, modulo $998244353$.
Sample
Sample 1
Input
4 5
Output
28672
For example, a maze like this satisfies the conditions. There are $28672$ mazes satisfying the conditions, such as this one.
Conversely, a maze like this does not satisfy the conditions, because the pill bug, given its habits, gets stuck at cell $(2, 5)$.
Sample 2
Input
6 1
Output
1
Only the maze with no obstacles placed on any cell of the grid satisfies the conditions.
Sample 3
Input
100 100
Output
865485495
Find the answer modulo $998244353$.
Sample 4
Input
1920 1080
Output
512501559
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
Magentor
Lucagon