問題文

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

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

制約

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

入力

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

$S$

出力

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

入力例 1

0001

出力例 1

8

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

入力例 2

110001

出力例 2

24

入力例 3

11101111011111000000000110000001111100011111000000001111111110000000111111111

出力例 3

697354558