配点 : $1100$ 点

問題文

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

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

制約

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

入力

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

$S$

出力

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

0001

8

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

110001

24

11101111011111000000000110000001111100011111000000001111111110000000111111111

697354558