← 返回题目列表

AtCoder · agc061_f

F. 完美弦乐

中文机器翻译题面 查看原题

分数: 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