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;

int N, minL[309][309], f[309][2], dp[609][609];
char sir[309];
const int mod = 998244353;

int add (int x, int y) {int ans = x + y; if (ans >= mod) ans -= mod; return ans;}
int subtract (int x, int y) {if (x >= y) return x - y; return x - y + mod;}
int mul (int x, int y) {return 1LL * x * y % mod;}
void adto (int &x, int y) {x += y; if (x >= mod) x -= mod;}

int power (int a, int b)
{
    int p = 1;
    for (int i=0; (1<<i) <= b; i++)
    {
        if (b & (1 << i)) p = mul (p, a);
        a = mul (a, a);
    }
    return p;
}

int fac[2000009], inv[2000009];
void Prec (int lim){fac[0] = inv[0] = 1;for (int i=1; i<=lim; i++)fac[i] = mul (fac[i - 1], i);
inv[lim] = power (fac[lim], mod - 2);for (int i=lim - 1; i>=0; i--)inv[i] = mul (inv[i + 1], i + 1);}
int comb (int N, int K){if (K > N || N < 0 || K < 0) return 0; int ans = mul (fac[N], inv[N - K]);ans = mul (ans, inv[K]);return ans;}

int dp2[309][309][309];
bool ok (int k0, int k1, int L)
{
    for (int j=0; j<=N / 2; j++)
        if (dp2[L][j][k0] >= k1)
            return 1;
    return 0;
/*    int k[2], curr = 0, future = 0, borrowed = 0;
    bool started = 0;
    if (k0 == 1 && k1 == 1 && L == 4)
        L = 4;
    k[0] = k0, k[1] = k1;
    for (int i=1; i<=L; i++)
    {
        int c = sir[i] - '0';
        if (f[i][c] + k[c] - 1 >= f[L][c])
        {
            if (started) started = 0;
            else
            if (future > 0) future --;
            else borrowed ++;
            k[c] --;
        }
        else
        {
            if (borrowed > 0) borrowed --;
            else
            if (started)
                future ++, started = 0;
            else
                started = 1;
        }
        if (future < 0 || curr < 0 || borrowed > 1)
            return 0;
    }
    return (borrowed == 0 && k[0] == 0 && k[1] == 0);*/
}

set < string > S;
bool ok (string s)
{
    int j = s.length () - 1, k0 = 0, k1 = 0, lastI = N + 1;
    for (auto c : s)
        if (c == '0') k0 ++;
        else k1 ++;
    for (int i=N; i>=1; i--)
    {
        lastI = i;
        while (s[j] != sir[i] && j>=0)
            j --;
        if (j < 0) break;
        j --;
        if (sir[i] == '0') k0 --;
        else k1 --;
    }
    return (minL[k0][k1] <= lastI);
}

void dfInsert (string s, char c);
void dfs (string s)
{
    if (S.find (s) != S.end ())
        return ;
    S.insert (s);
    if (s.size () >= 2)
    {
        char c0 = s[0], c1 = s[1];
        s.erase (s.begin ()), s.erase (s.begin ());
        if (c0 == c1)
            dfInsert (s, c0);
        else
            dfInsert (s, '0'),
            dfInsert (s, '1');
    }
}

void dfInsert (string s, char c)
{
    for (int i=0; i<=s.length (); i++)
    {
        string s2 = s;
        s2.insert (i, 1, c);
        dfs (s2);
    }
}

void updateMax (int &x, int y)
{
    if (y > x)
        x = y;
}

/*int maxF (int c)
{
    int cnt = 0, ans = 0;
    for (int i=1; i<=N; i++)
    {
        if (s[i])
    }
}*/

int main ()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);

scanf ("%s", sir + 1), N = strlen (sir + 1);
/*string init = sir + 1;
dfs (init);
printf ("%d\n", S.size ());*/
/*for (auto s: S)
    printf ("%s\n", s.c_str ());
return 0;*/
for (int i=1; i<=N; i++)
{
    f[i][0] = f[i - 1][0];
    f[i][1] = f[i - 1][1];
    f[i][sir[i] - '0'] ++;
}
for (int i=0; i<=N; i++)
    for (int q=0; q<=N / 2; q++)
        for (int j=0; j<=N; j++)
            dp2[i][q][j] = -4 * N;
dp2[0][0][0] = 0;
for (int i=0; i<N; i++)
    for (int q=0; q<=N / 2; q++)
        for (int j=0; j<=N; j++)
            if (dp2[i][q][j] >= 0)
            {
                ///not take the next 2
                if (i + 2 <= N)
                    updateMax (dp2[i + 2][q + 1][j], dp2[i][q][j]);
                if (q > 0)
                {
                    ///take sir[i + 1]
                    if (sir[i + 1] == '0')
                        updateMax(dp2[i + 1][q - 1][j + 1], dp2[i][q][j]);
                    else
                        updateMax(dp2[i + 1][q - 1][j], dp2[i][q][j] + 1);
                }
                if (i + 2 <= N)
                {
                    ///take one of sir[i + 1], sir[i + 2]
                    char c0 = sir[i + 1], c1 = sir[i + 2];
                    if (c0 == '0' || c1 == '0')
                        updateMax(dp2[i + 2][q][j + 1], dp2[i][q][j]);
                    if (c0 == '1' || c1 == '1')
                        updateMax(dp2[i + 2][q][j], dp2[i][q][j] + 1);
                }
            }
for (int k0=0; k0<=N; k0++)
    for (int k1=0; k0 + k1<=N; k1++)
    {
        minL[k0][k1] = k0 + k1;
        while (minL[k0][k1] <= N && !ok (k0, k1, minL[k0][k1]))
            minL[k0][k1] ++;
       // if (minL[k0][k1] <= N)
         //   printf ("(%d, %d) -> %d\n", k0, k1, minL[k0][k1]);
    }
/*int cnt = 0;
for (int L=1; L<=N; L++)
    for (int msk = 0; msk < (1 << L); msk ++)
    {
        string s;
        for (int i=0; i<L; i++)
            if ((msk >> i) & 1)
                s.push_back ('1');
            else
                s.push_back ('0');
        if (ok (s))
        {
            printf ("%s", s.c_str ());
            if (S.find (s) == S.end ())
                printf (" WA");
            S.erase (s);
            printf ("\n");
            cnt ++;
        }
    }
for (auto s : S)
    printf ("%s WA2\n", s.c_str ());*/
dp[0][0] = 1;
for (int i=0; i<=N; i++)
    for (int j=0; j<=N; j++)
        for (int k=0; j+k<=N; k++)
            adto (dp[i + 1][j + k], dp[i][j]);
//printf ("%d\n%d\n", cnt, S.size ());
int ans = 0;
for (int maxS = 0; maxS <= N; maxS ++)
{
    int f[2]; f[0] = 0, f[1] = 0;
    if (maxS == 0) f[(sir[N] - '0') ^ 1] = 1;
    else
    {
        f[(sir[N] - '0') ^ 1] = 1;
        for (int i=N - 1; i>=N - maxS; i--)
            f[(sir[i] - '0') ^ 1] ++;
    }
//    printf ("%d -> (%d, %d)\n", maxS, f[0], f[1]);
    for (int k0=0; k0<=N; k0++)
        for (int k1=0; k0 + k1<=N; k1++)
            if (minL[k0][k1] <= N - maxS && k0 + k1 + maxS > 0)
            {
                adto (ans, mul (dp[f[0]][k0], dp[f[1]][k1]));
  //              printf ("(%d, %d) -> +%d\n", k0, k1, mul (dp[f[0]][k0], dp[f[1]][k1]));
            }
}
printf ("%d\n", ans);
return 0;
}