問題一覧 > 通常問題

No.2802 Pill Bug in Grid Maze

レベル : / AI推定難易度 : 1900 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 26
作問者 : 👑 loop0919 / テスター : Magentor hiro1729 👑 獅子座じゃない人 Lucagon Basin-Bug mitu24472
お気に入りにしたユーザー ProblemId : 10256 / 自分の提出
問題文最終更新日: 2024-07-10 15:21:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original

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.

A pill bug has the habit of repeating the following actions forever.

  • 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もしくは右上の雲マークをクリックしてアカウントを作成してください。