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;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 303, M = 998244353;

int n;
char a[N];

bool can[N][N][N];

int dp[N][N][N];

void solv()
{
    scanf(" %s", (a + 1));
    for (n = 1; a[n]; ++n){}
    --n;
    can[0][0][0] = true;
    for (int i = 0; i <= n; ++i)
    {
        for (int q0 = n; q0 >= 0; --q0)
        {
            for (int q1 = n; q1 >= 0; --q1)
            {
                if (i == n - 1 && q0 == 1 && q1 == 0)
                    printf("");
                if (!can[i][q0][q1])
                    continue;
                if (q0 >= 2)
                    can[i][q0 - 1][q1] = true;
                if (q1 >= 2)
                    can[i][q0][q1 - 1] = true;
                if (q0 >= 1 && q1 >= 1)
                {
                    can[i][q0][q1 - 1] = true;
                    can[i][q0 - 1][q1] = true;
                }
                if (i < n)
                {
                    if (a[i + 1] == '0')
                    {
                        if (q0 >= 1)
                            can[i + 1][q0][q1] = true;
                        if (q1 >= 1)
                        {
                            can[i + 1][q0 + 1][q1 - 1] = true;
                            can[i + 1][q0][q1] = true;
                        }
                    }
                    else
                    {
                        if (q0 >= 1)
                        {
                            can[i + 1][q0 - 1][q1 + 1] = true;
                            can[i + 1][q0][q1] = true;
                        }
                        if (q1 >= 1)
                            can[i + 1][q0][q1] = true;
                    }
                }
                if (i + 1 < n)
                {
                    if (a[i + 1] == a[i + 2])
                    {
                        if (a[i + 1] == '0')
                            can[i + 2][q0 + 1][q1] = true;
                        else
                            can[i + 2][q0][q1 + 1] = true;
                    }
                    else
                    {
                        can[i + 2][q0 + 1][q1] = true;
                        can[i + 2][q0][q1 + 1] = true;
                    }
                }
            }
        }
    }

    dp[n + 1][0][0] = 1;
    for (int i = n + 1; i >= 1; --i)
    {
        for (int q0 = 0; q0 <= n; ++q0)
        {
            for (int q1 = 0; q1 <= n; ++q1)
            {
                // 0
                if (a[i] == '0')
                    dp[i][q0][q1] = (dp[i][q0][q1] + dp[i + 1][q0][q1]) % M;
                else if (q0 >= 1)
                    dp[i][q0][q1] = (dp[i][q0][q1] + dp[i][q0 - 1][q1]) % M;
                // 1
                if (a[i] == '1')
                    dp[i][q0][q1] = (dp[i][q0][q1] + dp[i + 1][q0][q1]) % M;
                else if (q1 >= 1)
                    dp[i][q0][q1] = (dp[i][q0][q1] + dp[i][q0][q1 - 1]) % M;
            }
        }
    }

    int ans = 0;
    for (int q0 = 0; q0 <= n; ++q0)
    {
        for (int q1 = 0; q1 <= n; ++q1)
        {
            int yq0 = q0, yq1 = q1;
            for (int i = n; i >= 0; --i)
            {
                if (can[i][yq0][yq1])
                {
                    ans = (ans + dp[i + 1][yq0][yq1]) % M;
                    break;
                }
                if (a[i] == '0')
                    --yq0;
                else
                    --yq1;
            }
        }
    }
    printf("%d\n", ans);
}

int main()
{
    #ifdef SOMETHING
    freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // SOMETHING
    //ios_base::sync_with_stdio(false), cin.tie(0);
    solv();
    return 0;
}

//while ((double)clock() / CLOCKS_PER_SEC <= 0.9){}