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>
#include <list>
using namespace std;
const int MAX=3e2+5,mod=998244353,inf=0x3f3f3f3f;
#define X first
#define Y second
#define pb push_back
using ll=long long;
typedef pair < int , int > ii;
int n;
char s[MAX];
bool a[MAX],c[MAX][MAX][MAX];
int f[MAX][MAX][MAX];
int sum[MAX];
void check(){
    cout<<n<<'\n';
    ll ans1=1;
    for(int i=1;i<n;i++){
        for(int b=0;b<(1<<i);b++){
            int dem=n,mm=0,uu=0;
            for(int j=0;j<i;j++){
                if((b&(1<<j))!=0){
                    if(a[dem]){
                        dem--;
                    }
                    else uu++,mm++;
                }
                else {
                    if(!a[dem]){
                        dem--;
                    }
                    else uu++;
                }
            }
            if(c[dem][uu][mm]) ans1++;
        }
    }
    cout<<ans1<<'\n';
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>s+1;
    n=strlen(s+1);
    c[0][0][0]=1;
    a[1]=s[1]-'0';
    c[1][0][0]=1;

    for(int i=2;i<=n;i++){
        a[i]=s[i]-'0';
        c[i][0][0]=1;
        if(a[i]){
            for(int j=1;j<=i/2;j++){
                c[i][j][0]|=c[i-1][j][0];
                for(int k=1;k<=j;k++)
                    c[i][j][k]|=c[i-1][j][k] | c[i-2][j-1][k-1] | c[i-1][j][k-1];
            }
        }
        else{
            for(int j=1;j<=i/2;j++){
                c[i][j][j]|=c[i-1][j][j];
                for(int k=0;k<j;k++)
                    c[i][j][k]|=c[i-1][j][k] | c[i-2][j-1][k] | c[i-1][j][k+1];
            }
        }
        if(a[i-1]){
            for(int j=1;j<=i/2;j++)
                for(int k=1;k<=j;k++)
                    c[i][j][k]|=c[i-2][j-1][k-1];
        }
        else{
            for(int j=1;j<=i/2;j++)
                for(int k=0;k<j;k++)
                    c[i][j][k]|=c[i-2][j-1][k];
        }
    }
    ll ans=1;
    for(int i=n;i>0;i--){
        sum[i]=sum[i+1]+a[i];
    }
    f[n+1][n+1][0]=1;
    for(int i=n;i>1;i--){
        for(int k=n-i+1,j=n+1;k>=0;k--){
            if(a[j-1]) f[i][j][k]+=f[i+1][j][k];
            else if(k>0)f[i][j][k]+=f[i+1][j][k-1];
            if(f[i][j][k]>=mod) f[i][j][k]-=mod;
            //cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<'\n';
            if(c[j-1][j-i][k-sum[j]])
                    ans+=f[i][j][k];
        }
        for(int j=n;j>=i;j--){
            for(int k=n-i+1;k>=sum[j];k--){
                if(a[j]) f[i][j][k]=f[i+1][j+1][k-1];
                else f[i][j][k]=f[i+1][j+1][k];
                if(a[j-1]) f[i][j][k]+=f[i+1][j][k];
                else if(k>0)f[i][j][k]+=f[i+1][j][k-1];
                if(f[i][j][k]>=mod) f[i][j][k]-=mod;
                //cout<<i<<' '<<j<<' '<<k<<' '<<f[i][j][k]<<'\n';
                if(c[j-1][j-i][k-sum[j]])
                    ans+=f[i][j][k];
            }
        }
    }
    //check();
    //for(int i=1;i<=n;i++)for(int j=1;j<=i/2;j++)for(int k=0;k<=j;k++) cout<<i<<' '<<j<<' '<<k<<' '<<c[i][j][k]<<'\n';

    cout<<ans%mod;
}