题目描述

正の整数 $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$ で割った余りを求めてください。

输入格式

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

$N$ $M$

输出格式

答えを出力せよ。

题目大意

有正整数 $n,m$，称一个非空 $01$ 串是好的当且仅当串中 $1$ 的个数是 $n$ 的倍数，$0$ 的个数是 $m$ 的倍数。

一个串是完美的，当且仅当其是好的，且其所有非空子串均不是好的。

对于给定的 $n,m$，求完美的串的个数，答案对 $998244353$ 取模。

2 2

4

3 2

7

23 35

212685109

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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