{"problem":{"name":"Perfect Strings","description":{"content":"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$. *   T","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":10000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc061_f"},"statements":[{"statement_type":"Markdown","content":"There are positive integers $N$ and $M$.\nA binary string $s$ is called **good** if all of the followings are satisfied:\n\n*   $s$ is non-empty.\n*   The number of `1`s in $s$ is a multiple of $N$.\n*   The number of `0`s in $s$ is a multiple of $M$.\n\nA 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.\nOne can show that for any $N, M$ the number of perfect strings is finite. Find this number modulo $998\\,244\\,353$.\n\n## Constraints\n\n*   $1 \\leq N, M \\leq 40$\n*   All values in the input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc061_f","tags":[],"sample_group":[["2 2","4\n\nThe perfect strings are `00`, `0101`, `1010`, `11`."],["3 2","7\n\nThe perfect strings are `00`, `01011`, `01101`, `10101`, `10110`, `11010`, `111`."],["23 35","212685109"]],"created_at":"2026-03-03 11:01:14"}}