/ 
Time Limit: 10 sec / Memory Limit: 1024 MB
配点 : 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
出力
答えを出力せよ。
入力例 1
2 2
出力例 1
4
完璧な文字列は 00, 0101, 1010, 11 です。
入力例 2
3 2
出力例 2
7
完璧な文字列は 00, 01011, 01101, 10101, 10110, 11010, 111 です。
入力例 3
23 35
出力例 3
212685109
Score : 2000 points
Problem Statement
There are positive integers N and M.
A binary string s is called good if all of the followings are satisfied:
- s is non-empty.
- The number of
1s in s is a multiple of N. - The number of
0s in s is a multiple of M.
A good string is called perfect if it doesn't contain shorter good (contiguous) substrings. For example, if N = 3 and M = 2, then strings 111, 00 and 10101 are perfect, but 0000 and 11001 are not.
One can show that for any N, M the number of perfect strings is finite. Find this number modulo 998\,244\,353.
Constraints
- 1 \leq N, M \leq 40
- All values in the input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print the answer.
Sample Input 1
2 2
Sample Output 1
4
The perfect strings are 00, 0101, 1010, 11.
Sample Input 2
3 2
Sample Output 2
7
The perfect strings are 00, 01011, 01101, 10101, 10110, 11010, 111.
Sample Input 3
23 35
Sample Output 3
212685109