D - Secret Passage Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1100 点

問題文

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

Score : 1100 points

Problem Statement

Given is a string S consisting of 0 and 1. Find the number of strings, modulo 998244353, that can result from applying the following operation on S zero or more times:

  • Remove the two characters at the beginning of S, erase one of them, and reinsert the other somewhere in S. This operation can be applied only when S has two or more characters.

Constraints

  • 1 \leq |S| \leq 300
  • S consists of 0 and 1.

Input

Input is given from Standard Input in the following format:

S

Output

Print the number of strings, modulo 998244353, that can result from applying the operation on S zero or more times.

Sample Input 1

0001

Sample Output 1

8

Eight strings, 0001, 001, 010, 00, 01, 10, 0, and 1, can result.

Sample Input 2

110001

Sample Output 2

24

Sample Input 3

11101111011111000000000110000001111100011111000000001111111110000000111111111

Sample Output 3

697354558