Score : 1400 points
Consider the following set of rules for encoding strings consisting of 0
and 1
:
0
and 1
can be encoded as 0
and 1
, respectively. (
Px
K)
.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:
0
and 1
;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.
0
and 1
.Input is given from Standard Input in the following format:
S
Print the total number of distinct encodings of all subsets of S modulo 998244353.
011
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.
0000
10
This time S has only one subset, but it can be encoded in 10 different ways.
101110
156
001110111010110001100000100111
363383189
Don't forget to take the result modulo 998244353.