問題一覧 > 通常問題

No.2303 Frog on Grid

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 74
作問者 : Shirotsume / テスター : 👑 ygussany kaichou243
3 ProblemId : 9468 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-05-03 01:28:13

問題文

二次元平面上の点 (0,0)(0, 0) にカエルがいます．カエルが点 (i,j)(i, j) にいるとき，ジャンプを行うことで点 (i+1,j),(i,j+1),(i+2,j),(i,j+2)(i + 1, j), (i, j + 1), (i + 2, j), (i, j + 2) のいずれかに着地することができます．

カエルはジャンプを繰り返して点 (H,W)(H, W) まで移動しようとしています．移動方法の個数を 998244353998244353 で割った余りを求めてください．

22 つの移動方法は，カエルが移動の過程で着地した点の集合が異なる場合に区別されるものとします．

制約

  • 入力は全て整数
  • 1≤H,W≤2×1051 \leq H, W \leq 2 \times 10^5

入力

入力は標準入力から以下の形式で与えられる．

HH WW

出力

答えを出力せよ．

サンプル

サンプル1
入力
2 3
出力
32

カエルの移動方法は全部で 3232 通りあります．例えば，以下のような移動が考えられます．

  • (0,0)→(0,1)→(0,2)→(2,2)→(2,3)(0, 0) \rightarrow (0, 1) \rightarrow (0, 2) \rightarrow (2, 2) \rightarrow (2, 3)
  • (0,0)→(2,0)→(2,2)→(2,3)(0, 0) \rightarrow (2, 0) \rightarrow (2, 2) \rightarrow (2, 3)
サンプル2
入力
100 100
出力
853998634
サンプル3
入力
100000 200000
出力
664894518

998244353998244353 で割った余りを求めてください．

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。