题目描述

次のような、0 と 1 からなる文字列をエンコードする規則を考えます。

• 文字列 0、1 はそれぞれ 0、1 とエンコードできる。
• 文字列 $A$、$B$ をそれぞれ $P$、$Q$ とエンコードできる場合、文字列 $AB$ を $PQ$ とエンコードできる。
• 文字列 $A$ を $P$ とエンコードできる場合、$K\ \geq\ 2$ を正の整数として、文字列 $AA...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$ で割ったあまりを出力せよ。

题目大意

我们定义一个 01 串的压缩是满足如下方式的字符串变化过程：

• $0\rightarrow 0,1\rightarrow 1$
• 如果 $A\rightarrow P,B\rightarrow Q$ 合法，那么 $A+B\rightarrow P+Q$ 也合法（其中 $+$ 代表字符串拼接）
• 如果 $S=\underbrace{A+A+\cdots+A}_{n\text{个}(n\ge 2)}$，那么 $S\rightarrow(A\times n)$ 也合法（其中 (, ), × 为字符，$n$ 为数字，算作一个字符，即使其中有 $0/1$）

我们同时定义 $01$ 串 $B$ 是 $A$ 的子集当且仅当：

• $|A|=|B|$
• $\forall B_i=1,A_i=1$

现在给你一个 $01$ 串 $S$，问它所有的子集的合法变化结果数的总和为多少。

答案对 $998244353$ 取模。

011

9

0000

10

101110

156

001110111010110001100000100111

363383189

提示

制約

• $1\ \leq\ |S|\ \leq\ 100$
• $S$ は 0 と 1 からなる。

Sample Explanation 1

$S$ のサブセットは $4$ 個存在し、 - 011 は 011、0(1x2) とエンコードできます。 - 010 は 010 とエンコードできます。 - 001 は 001、(0x2)1 とエンコードできます。 - 000 は 000、0(0x2)、(0x2)0、(0x3) とエンコードできます。 したがって、$S$ のすべてのサブセットについてのエンコード方法の個数の総和は $2\ +\ 1\ +\ 2\ +\ 4\ =\ 9$ 通りです。

Sample Explanation 2

今回は $S$ のサブセットは $1$ 個しか存在しませんが、$10$ 通りの方法でエンコードできます。

Sample Explanation 4

結果を $998244353$ で割ったあまりを出力することを忘れずに。