分数: 1400 点
问题陈述
考虑以下一组规则来对由以下内容组成的字符串进行编码 0 和 1:
- 字符串
0和1可以编码为0和1。 - 如果字符串 A 和 B 可以编码为 P 和 Q分别,然后字符串 AB 可以编码为 PQ.
- 如果字符串 A 可以编码为 P 和 K \geq 2 是正整数,则字符串 AA...A (A 重复 K 次)可以编码为
(PxK).
例如,字符串 001001001除其他可能性外,可以编码为 001001001, 00(1(0x2)x2)1 和 (001x3).
让我们调用字符串 A 字符串的子集 B 如果:
- A 和 B 长度相等并且由以下组成
0和1; - 对于所有指数 i 这样 A_i =
1,这也是事实 B_i =1.
给你字符串 S 组成 0 和 1。找到所有子集的不同编码的总数 S,模数 998244353.
约束
- 1 \leq |S| \leq 100
- S 包括
0和1.
输入
输入由标准输入按以下格式给出:
S
输出
打印所有子集的不同编码总数 S 模数 998244353.
示例输入 1
011
示例输出 1
9
有四个子集 S:
011可以编码为011和0(1x2);010可以编码为010;001可以编码为001和(0x2)1;000可以编码为000,0(0x2),(0x2)0和(0x3).
因此,所有子集的编码总数 S is 2 + 1 + 2 + 4 = 9.
示例输入 2
0000
示例输出 2
10
这次 S 只有一个子集,但可以编码为 10 不同的方式。
示例输入 3
101110
示例输出 3
156
示例输入 4
001110111010110001100000100111
示例输出 4
363383189
不要忘记对结果取模 998244353.