题目描述

考虑一种对仅包含 0 和 1 的字符串进行编码的规则如下：

• 字符串 0 和 1 分别可以被编码为 0 和 1。
• 如果字符串 $A$ 和 $B$ 分别可以被编码为 $P$ 和 $Q$，则字符串 $AB$ 可以被编码为 $PQ$。
• 如果字符串 $A$ 可以被编码为 $P$，且 $K \geq 2$ 为正整数，则字符串 $AA\ldots A$（将 $A$ 连续拼接 $K$ 次）可以被编码为 ($P$x$K$)。

例如，字符串 001001001 可以被编码为 001001001、00(1(0x2)x2)1、(001x3) 等，还有其他的编码方式。

此外，当满足以下条件时，称字符串 $A$ 是字符串 $B$ 的「子集」：

• $A$ 和 $B$ 长度相等，且都只包含 0 和 1。
• 对于所有 $A_i$ 为 1 的下标 $i$，$B_i$ 也为 1。

给定一个只由 0 和 1 组成的字符串 $S$，请对于 $S$ 的所有子集，分别求出每个子集的编码方法数，并求这些数量的总和对 $998244353$ 取模后的结果。

输入格式

输入通过标准输入给出，如下所示：

$S$

输出格式

输出 $S$ 的所有子集的编码方法数之和对 $998244353$ 取模的值。

样例 1

输入

011

输出

9

样例 2

输入

0000

输出

10

样例 3

输入

101110

输出

156

样例 4

输入

001110111010110001100000100111

输出

363383189

说明/提示

限制条件

• $1 \leq |S| \leq 100$
• $S$ 仅包含字符 0 和 1。

样例解释 1

$S$ 的子集有 $4$ 个：

• 011 可以编码为 011、0(1x2)。
• 010 可以编码为 010。
• 001 可以编码为 001、(0x2)1。
• 000 可以编码为 000、0(0x2)、(0x2)0、(0x3)。

因此，所有子集的编码方法数总和为 $2 + 1 + 2 + 4 = 9$。

样例解释 2

本例中 $S$ 仅有 $1$ 个子集，其编码方式有 $10$ 种。

样例解释 4

不要忘记，最后的答案需要对 $998244353$ 取模。

由 ChatGPT 5 翻译