题目描述

0 と 1 のみからなる文字列 $S$ が与えられます。以下の操作を $0$ 回以上任意の回数繰り返してできる可能性のある文字列の個数を $998244353$ で割った余りを求めてください。

• $S$ の先頭 $2$ 文字を取り除き、そのうち片方を捨て、もう片方を $S$ の任意の位置に挿入する。この操作は、$S$ が $2$ 文字以上からなるときのみ実行できる。

输入格式

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

$S$

输出格式

操作を $0$ 回以上任意の回数繰り返してできる可能性のある文字列の個数を $998244353$ で割った余りを出力せよ。

题目大意

给定 $01$ 串 $S$，每次操作位：选择首位两个字符，删除其中一个字符，把另一个字符插到任意位置。求最后能得到多少种不同的 $01$ 串。

其中 $1\le |S|\le 300$。

0001

8

110001

24

11101111011111000000000110000001111100011111000000001111111110000000111111111

697354558

提示

制約

• $1\ \leq\ |S|\ \leq\ 300$
• $S$ は 0 と 1 のみからなる

Sample Explanation 1

0001, 001, 010, 00, 01, 10, 0, 1 の $8$ つが条件を満たします。