#1171. 恋恋的困难题

内存限制:512 MiB 时间限制:3000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Komeiji Koishi

题目描述

给你一个只有0,10,1组成的字符串SS,如果SS的长度大于11,那么你可以对它进行一次如下操作:

SS的前两个字符中,选择其中一个删掉,并将另一个字符插到SS的任意位置。

比如,操作前SS101110101110,一次操作,你可以将第一个元素11删掉,将第二个元素00插到剩下的第一个11后面,得到新的字符串1011010110,你也可以将这个00插到第一个11前面,得到0111001110

你可以随意进行若干次这样的操作(注意操作只能在字符串长度大于11时进行,因此最多做S1|S|-1次操作),那么最后得到的字符串SS' 有多少种不同的可能?将答案模998244353998244353输出。

输入格式

一行一个0101SS

输出格式

一行一个非负整数表示答案

样例

样例输入1

1101011

样例输出1

38

样例输入2

00011001100100011110001100

样例输出2

483120

样例输入3

01010

样例输出3

19

样例输入4

1100010101001100010101100111000010110101010101010101001000001010101010100111111000101011100000

样例输出4

546831414

数据范围与提示

1S3001\leq |S|\leq 300