問題一覧 > 通常問題

No.1186 長方形の敷き詰め

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 138
作問者 : NatsubiSoganNatsubiSogan / テスター : kaagekaage
25 ProblemId : 4676 / 出題時の順位表
問題文最終更新日: 2020-08-29 12:52:33

問題文

あなたは縦 $1$、横 $N$ の形をした長方形のピースを無数に持っています。

長方形を敷き詰めるのが大好きなNatsubiSoganは、あなたに以下の命令を出しました!

  • それらのピースを使って、縦 $N$ 、横 $M$ の長方形をすきまなく敷き詰めよ。

ここで「敷き詰める」とは、ピースを割ったり、ピースを重ねたり、長方形からピースをはみ出させたりせずに、長方形のすべての領域について、 ちょうど $1$ つのピースがその領域を覆っている状態にすることを指します。例えば、ピースを斜めに並べて敷き詰めることはできません。

あいにく、あなたはパズルがとても苦手です。そこで、この敷き詰め方が何通りあるかコンピューターを使って調べることにしました。

この答えを $998244353$ で割ったあまりを出力しなさい。

ただし、縦 $1$、横 $N$ のピースは自由に回転させて良いものとし、全体の長方形を回転・反転して同じになる敷き詰め方も区別して数えるものとします。

入力

$N\ M$

  • 入力はすべて整数
  • $1 \leq N \leq 10^9$
  • $1 \leq M \leq 10^6$

出力

答えを $998244353$ で割ったあまりを1行に出力してください。
最後に改行してください。

サンプル

サンプル1
入力
2 4
出力
5


画像の通り、 $5$ 通りの並べ方が考えられます。

サンプル2
入力
3 4
出力
3


画像の通り、 $3$ 通りの並べ方が考えられます。

サンプル3
入力
1000000000 1000000
出力
1

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