题目描述

给定正整数 $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$

输出格式

输出答案。

样例 1

输入

2 2

输出

4

样例 2

输入

3 2

输出

7

样例 3

输入

23 35

输出

212685109

说明/提示

限制

• $1 \leq N,\ M \leq 40$
• 输入中的值均为整数。

样例解释 1

完美字符串为 00、0101、1010、11。

样例解释 2

完美字符串为 00、01011、01101、10101、10110、11010、111。

由 ChatGPT 4.1 翻译