[AGC020E] Encoding Subsets

我们定义一个 `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$ 取模。

[problemUrl]: https://atcoder.jp/contests/agc020/tasks/agc020_e 次のような、`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 $ で割ったあまりを出力せよ。

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 $ で割ったあまりを出力することを忘れずに。