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
1
s in s is a multiple of N. - The number of
0
s 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