問題文

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

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

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

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

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

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

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

入力

$NM$

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

出力

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

サンプル

2 4

5

3 4

3

1000000000 1000000

1