分数: 2000 点
问题陈述
有正整数 N 和 M.
二进制字符串 s 被称为 好 如果满足以下所有条件:
- s 非空。
- 数量
1位于 s 是的倍数 N. - 数量
0位于 s 是的倍数 M.
好的字符串叫做 完美 如果它不包含较短的好(连续)子字符串。例如,如果 N = 3 和 M = 2,然后是字符串 111, 00 和 10101 很完美,但是 0000 和 11001 不是。
可以证明对于任何 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