Beautiful Palindrome

2 secs 1024 MB
loop0919's icon loop0919

問題文

NN 種類の(スペースでない)文字があり、それらをまとめてループ文字と呼びます。

あなたは次の条件をすべて満たす、ループ文字とスペースからなる長さ MM の文字列を書くことにしました。

  • 11 文字目と MM 文字目にはループ文字が書かれている。
  • ループ文字は等間隔に書かれている。つまり、ある非負整数 kk が存在して、11 個のループ文字と kk 個のスペースが交互に書かれている。
  • 文字列は回文になっている。

条件を満たす文字列の個数を求めてください。答えが非常に大きくなる場合があるため、 998244353998244353 で割った余りを出力してください。

制約

  • N,MN, M1N,M1091 \le N, M \le 10^9 を満たす整数である。

入力

入力は以下の形式で与えられる。

入力

NNMM

出力

条件を満たすような文字列の個数を 998244353998244353 で割った余りを答えてください。

サンプル

サンプル 1

入力
2 5
出力
14

便宜上ループ文字を a , b 、スペースを - とします。

条件を満たす文字列は a---a , b---b , a-a-a , a-b-a , b-a-b , b-b-b , aaaaa , aabaa , ababa , abbba , baaab , babab , bbabb , bbbbb1414 個です。

サンプル 2

入力
3141592 653589
出力
942683476

998244353998244353 で割った余りを求めることを忘れないようにしてください。

Submit


Go (1.21)