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;
typedef long long ll;
const int mod=998244353;
inline void _add(int &a,int b)
{
    if((a+=b)>=mod)a-=mod;
}
inline int add(int a,int b)
{
    if((a+=b)>=mod)a-=mod;
    return a;
}
inline int dec(int a,int b)
{
    if((a-=b)<0)a+=mod;
    return a;
}
inline int mult(int a,int b)
{
    ll t=(ll)a*b;
    if(t>=mod)t%=mod;
    return t;
}
inline int power(int a,int b)
{
    int out=1;
    while(b)
    {
        if(b&1)out=mult(out,a);
        a=mult(a,a);
        b>>=1;
    }
    return out;
}
char s[310];
bool f[310][310][310],g[310][310][310];
int n,ss[310][310][310];
void trans(int i,int j,int k,int c1,int c2)
{
    f[i+1][j+(c1==0)][k+(c1==1)]=1;
    f[i+1][j+(c2==0)][k+(c2==1)]=1;
}
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    f[0][0][0]=1;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<=i;j++)
        {
            for(int k=0;j+k<=i;k++)
            {
                int pos=i+j+k+1;
                if(pos>n+1)continue;
                if(!f[i][j][k])continue;
                if(pos<=n-1)
                {
                    trans(i,j,k,s[pos]-'0',s[pos+1]-'0');
                }
                if(pos<=n)
                {
                    if(j)
                    {
                        trans(i,j-1,k,s[pos]-'0',0);
                    }
                    if(k)
                    {
                        trans(i,j,k-1,s[pos]-'0',1);
                    }
                }
                if(j>=2)trans(i,j-2,k,0,0);
                if(j&&k)trans(i,j-1,k-1,0,1);
                if(k>=2)trans(i,j,k-2,1,1);
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<=i;j++)
        {
            for(int k=0;j+k<=i;k++)
            {
                int pos=i+j+k+1;
                if(pos>n+1)continue;
                g[pos][j][k]=f[i][j][k];
            }
        }
    }
    for(int i=n+1;i>=2;i--)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                int c=s[i-1]-'0';
                if(!c)
                {
                    if(j)g[i-1][j-1][k]|=g[i][j][k];
                }
                else
                {
                    if(k)g[i-1][j][k-1]|=g[i][j][k];
                }
            }
        }
    }
    int res=0;
    ss[n+1][0][0]=1;
    for(int sum=n+1;sum>=1;sum--)
    {
        for(int len=sum;len<=n+1;len++)
        {
            int up=len-sum;
            for(int j=0;j<=up;j++)
            {
                int k=up-j;
                if(s[len-1]=='0')
                {
                    _add(ss[len-1][j][k],ss[len][j][k]);
                    _add(ss[len][j][k+1],ss[len][j][k]);
                }
                else
                {
                    _add(ss[len][j+1][k],ss[len][j][k]);
                    _add(ss[len-1][j][k],ss[len][j][k]);
                }    
            }
        }
    }
    // for(int i=n+1;i>=1;i--)
    // {
    //     for(int j=0;j<=n;j++)
    //     {
    //         for(int k=0;k<=n;k++)cerr<<ss[i][j][k]<<' ';
    //         cerr<<'\n';
    //     }
    //     cerr<<'\n';
    // }
    for(int i=1;i<=n+1;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int k=0;k<=n;k++)
            {
                if(g[i][j][k])res=add(res,ss[i][j][k]);
            }
        }
    }
    printf("%d\n",res);
    return 0;
}