Problem: 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.

Examples

Input

0001


Output

8


Input

110001


Output

24


Input

11101111011111000000000110000001111100011111000000001111111110000000111111111


Output

697354558

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

const int Maxn = 305;
const int mod = 998244353;

string S;
bool pos[Maxn][Maxn][Maxn];
int dp[Maxn][Maxn][Maxn];
int res;

int main()
{
    cin >> S;
    pos[0][0][0] = true;
    for (int i = 0; i <= S.length(); i++)
        for (int a = Maxn - 1; a >= 0; a--)
            for (int b = Maxn - 1; b >= 0; b--) if (pos[i][a][b]) {
                if (a + b >= 2) {
                    if (a > 0) pos[i][a - 1][b] = true;
                    if (b > 0) pos[i][a][b - 1] = true;
                }
                if (i < S.length()) {
                    pos[i + 1][a][b] = true;
                    if (a > 0) pos[i + 1][a - 1 + (S[i] == '0')][b + (S[i] == '1')] = true;
                    if (b > 0) pos[i + 1][a + (S[i] == '0')][b - 1 + (S[i] == '1')] = true;
                }
                if (i + 1 < S.length()) {
                    pos[i + 2][a + (S[i] == '0')][b + (S[i] == '1')] = true;
                    pos[i + 2][a + (S[i + 1] == '0')][b + (S[i + 1] == '1')] = true;
                }
            }
    dp[S.length()][0][0] = 1;
    for (int i = S.length(); i > 0; i--)
        for (int a = 0; a < Maxn; a++)
            for (int b = 0; b < Maxn; b++) if (dp[i][a][b]) {
                if (pos[i][a][b]) res = (res + dp[i][a][b]) % mod;
                if (S[i - 1] == '0') dp[i - 1][a][b] = (dp[i - 1][a][b] + dp[i][a][b]) % mod;
                else if (a + 1 < Maxn) dp[i][a + 1][b] = (dp[i][a + 1][b] + dp[i][a][b]) % mod;
                if (S[i - 1] == '1') dp[i - 1][a][b] = (dp[i - 1][a][b] + dp[i][a][b]) % mod;
                else if (b + 1 < Maxn) dp[i][a][b + 1] = (dp[i][a][b + 1] + dp[i][a][b]) % mod;
            }
    printf("%d\n", res);
    return 0;
}