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:
//In the name of Allah
#include <bits/stdc++.h>

using namespace std;

#define F first
#define S second
#define MP make_pair
#define PB push_back
#define int long long
#define PII pair<int,int>

const int N=3e2+50;
const int mod=998244353;

string s;
int n;
bool dp[N][N][N];//len,matchs,zeros
int cnt[N][N][N];
int hl[]={0,0,1,1};
int hr[]={1,0,1,0};

int newM(int nm){
    return (nm==n)?-1:s[n-nm-1]-'0';
}

int32_t main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>s;
	/*for(int i=0;i<150;i++){
        s+="01";
	}*/
	n=s.size();
    if(n==1){
        cout<<1<<"\n";
        return 0;
    }
	for(int len=n;len>=1;len--){
        for(int m=0;m<=len;m++){
            for(int z=0;z<=len-m;z++){
                int o=len-m-z;
                bool& _dp=dp[len][m][z];
                if(len==n){
                    _dp=(m==n);
                    continue;
                }
                int match=s[n-m-1]-'0';
                for(int i=0;i<4;i++){
                    int np[]={z,o};
                    if(np[hr[i]]==0 && (m==0 || s[n-m]-'0'!=hr[i]))
                        continue;
                    int nm=m;
                    int nmatch=match;
                    if(np[hr[i]]!=0 && match==hr[i]){
                        nm++;
                        np[hr[i]]--;
                        nmatch=newM(nm);
                    }
                    np[hl[i]]++;
                    if(hl[i]==nmatch){
                        nm++;
                        np[hl[i]]--;
                    }
                    _dp|=dp[len+1][nm][np[0]];
                }
                for(int i=0;i<4;i++){
                    int np[]={z,o};
                    if(np[hr[i]]==0)
                        continue;
                    int nm=m;
                    int nmatch=match;
                    np[hl[i]]++;
                    if(hl[i]==nmatch){
                        nm++;
                        np[hl[i]]--;
                        nmatch=(nm==n)?-1:s[n-nm-1]-'0';
                    }
                    if(nmatch==hr[i]){
                        nm++;
                        np[hr[i]]--;
                    }
                    _dp|=dp[len+1][nm][np[0]];
                }
                if(m!=0 && newM(m)==s[n-m]-'0'){
                    _dp|=dp[len+1][m+1][z];
                }

            }
        }
	}
	//cout<<dp[2][0][2]<<"\n";
	cnt[0][0][0]=1;
	int ans=0;
	for(int len=1;len<=n;len++){
        for(int m=0;m<=len;m++){
            for(int z=0;z<=len-m;z++){
                int o=len-m-z;
                int& _cnt=cnt[len][m][z];
                int lm=(m==0)?-1:s[n-m]-'0';
                int lnm=(m==n)?-1:s[n-m-1]-'0';
                _cnt=0;
                if(m!=0)
                    _cnt=cnt[len-1][m-1][z];
                if(lnm!=1){
                    _cnt=(_cnt+cnt[len-1][m][z])%mod;
                }
                if(lnm!=0 && z>0){
                    _cnt=(_cnt+cnt[len-1][m][z-1])%mod;
                }
                if(dp[len][m][z]){
                    //cout<<len<<" "<<m<<" "<<z<<" "<<_cnt<<"\n";
                    ans=(ans+_cnt)%mod;
                }
            }
        }
	}
	cout<<ans<<"\n";



    return 0;
}