E - Encoding Subsets Editorial /

Time Limit: 5 sec / Memory Limit: 512 MB

配点 : 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 からなる。
  • A_i = 1 であるようなすべての添字 i に対して、B_i = 1 でもある。

0 と 1 からなる文字列 S が与えられます。S のすべてのサブセットについて、それぞれをエンコードする方法が何通り存在するか求め、それらの個数の総和を 998244353 で割ったあまりを求めてください。

制約

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

入力

入力は標準入力から以下の形式で与えられる。

S

出力

S のすべてのサブセットについてのエンコード方法の個数の総和を 998244353 で割ったあまりを出力せよ。

入力例 1

011

出力例 1

9

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 通りです。

入力例 2

0000

出力例 2

10

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

入力例 3

101110

出力例 3

156

入力例 4

001110111010110001100000100111

出力例 4

363383189

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

Score : 1400 points

Problem Statement

Consider the following set of rules for encoding strings consisting of 0 and 1:

  • Strings 0 and 1 can be encoded as 0 and 1, respectively.
  • If strings A and B can be encoded as P and Q, respectively, then string AB can be encoded as PQ.
  • If string A can be encoded as P and K \geq 2 is a positive integer, then string AA...A (A repeated K times) can be encoded as (PxK).

For example, string 001001001, among other possibilities, can be encoded as 001001001, 00(1(0x2)x2)1 and (001x3).

Let's call string A a subset of string B if:

  • A and B are equal in length and consist of 0 and 1;
  • for all indices i such that A_i = 1, it's also true that B_i = 1.

You are given string S consisting of 0 and 1. Find the total number of distinct encodings of all subsets of S, modulo 998244353.

Constraints

  • 1 \leq |S| \leq 100
  • S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the total number of distinct encodings of all subsets of S modulo 998244353.

Sample Input 1

011

Sample Output 1

9

There are four subsets of S:

  • 011 can be encoded as 011 and 0(1x2);
  • 010 can be encoded as 010;
  • 001 can be encoded as 001 and (0x2)1;
  • 000 can be encoded as 000, 0(0x2), (0x2)0 and (0x3).

Thus, the total number of encodings of all subsets of S is 2 + 1 + 2 + 4 = 9.

Sample Input 2

0000

Sample Output 2

10

This time S has only one subset, but it can be encoded in 10 different ways.

Sample Input 3

101110

Sample Output 3

156

Sample Input 4

001110111010110001100000100111

Sample Output 4

363383189

Don't forget to take the result modulo 998244353.