配点 : $2000$ 点

問題文

正の整数 $N, M$ があります。

0 と 1 からなる文字列 $s$ は、以下を全て満たすときに良いといわれます。

• $s$ は空でない。
• $s$ に含まれる 1 の個数は $N$ の倍数である。
• $s$ に含まれる 0 の個数は $M$ の倍数である。

良い文字列は、より短い良い文字列を（連続した）部分文字列として含まないときに完璧であるといわれます。例えば、$N = 3, M = 2$ のとき、文字列 111, 00, 10101 は完璧ですが、0000, 11001 は完璧ではありません。

任意の $N, M$ について、完璧な文字列の個数は有限であることが示せます。与えられた $N, M$ について、この個数を $998\,244\,353$ で割った余りを求めてください。

制約

• $1 \leq N, M \leq 40$
• 入力中の値は全て整数である。

入力

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

$N$ $M$

出力

答えを出力せよ。

2 2

4

完璧な文字列は 00, 0101, 1010, 11 です。

3 2

7

完璧な文字列は 00, 01011, 01101, 10101, 10110, 11010, 111 です。

23 35

212685109