[AGC046D] Secret Passage

题意翻译

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

题目描述

[problemUrl]: https://atcoder.jp/contests/agc046/tasks/agc046_d `0` と `1` のみからなる文字列 $ S $ が与えられます。以下の操作を $ 0 $ 回以上任意の回数繰り返してできる可能性のある文字列の個数を $ 998244353 $ で割った余りを求めてください。 - $ S $ の先頭 $ 2 $ 文字を取り除き、そのうち片方を捨て、もう片方を $ S $ の任意の位置に挿入する。この操作は、$ S $ が $ 2 $ 文字以上からなるときのみ実行できる。

输入输出格式

输入格式

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

输出格式

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

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

输入样例 #3

11101111011111000000000110000001111100011111000000001111111110000000111111111

输出样例 #3

697354558

说明

### 制約 - $ 1\ \leq\ |S|\ \leq\ 300 $ - $ S $ は `0` と `1` のみからなる ### Sample Explanation 1 `0001`, `001`, `010`, `00`, `01`, `10`, `0`, `1` の $ 8 $ つが条件を満たします。