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<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<list>
#include<bitset>
#include<stack>
#include<memory>
#include<numeric>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
#define REP(i, n) for(int i = 0;i < (n);i++)
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=998244353;
const llint inf=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-10;
template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}

int main(void){
	string S;cin>>S;
	int i,j,k,n=S.size();
	string T=S;
	REV(T);
	S=S+"2222222222";
	T=T+"2222222222";
	static int dpO[305][305]={};//地点、取得回数、0の最大数
	static int dpI[305][305]={};//地点、取得回数、1の最大数
	static int dpOa[305][305]={};//地点、取得回数、0の最大数 (未取得)
	static int dpIa[305][305]={};//地点、取得回数、1の最大数 (未取得)
	for(i=0;i<=n;i++){
		for(j=0;j<=i+2;j++){
			dpO[i][j]=-mod;
			dpOa[i][j]=-mod;
			dpI[i][j]=-mod;
			dpIa[i][j]=-mod;
		}
	}
	dpO[0][0]=0;
	dpI[0][0]=0;
	for(i=0;i<=n;i++){
		for(j=0;j<=i;j++){
			chmax(dpO[i][j],dpOa[i][j]);
			chmax(dpO[i+1][j],dpO[i][j]);
			chmax(dpOa[i+1][j],dpOa[i][j]);
			if(S[i]=='0'){chmax(dpO[i+1][j],dpOa[i][j]+1);}
			if(S[i]=='0'||S[i+1]=='0'){chmax(dpO[i+2][j+1],dpO[i][j]+1);}
			else{chmax(dpOa[i+2][j+1],dpO[i][j]);}
			if(S[i]=='0'&&dpO[i][j]!=j){chmax(dpO[i+1][j],dpO[i][j]+1);}
			
			chmax(dpI[i][j],dpIa[i][j]);
			chmax(dpI[i+1][j],dpI[i][j]);
			chmax(dpIa[i+1][j],dpIa[i][j]);
			if(S[i]=='1'){chmax(dpI[i+1][j],dpIa[i][j]+1);}
			if(S[i]=='1'||S[i+1]=='1'){chmax(dpI[i+2][j+1],dpI[i][j]+1);}
			else{chmax(dpIa[i+2][j+1],dpI[i][j]);}
			if(S[i]=='1'&&dpI[i][j]!=j){chmax(dpI[i+1][j],dpI[i][j]+1);}
			
			//cerr<<"i="<<i<<"j="<<j<<"dpO="<<dpO[i][j]<<"dpI="<<dpI[i][j]<<endl;
		}
	}
	
	static llint ep[305][305][305]={};//0の数,1の数、stringのいける数
	ep[0][0][0]=1;
	for(i=0;i<=n;i++){
		for(j=0;i+j<=n;j++){
			for(k=0;k<=i+j;k++){
				ep[i][j][k]%=mod;
				
				if(T[k]!='0'){ep[i+1][j][k]+=ep[i][j][k];}
				else{ep[i+1][j][k+1]+=ep[i][j][k];}
				
				if(T[k]!='1'){ep[i][j+1][k]+=ep[i][j][k];}
				else{ep[i][j+1][k+1]+=ep[i][j][k];}
			}
		}
	}
	for(i=0;i<=n;i++){
		for(j=0;i+j<=n;j++){
			for(k=i+j;k>=0;k--){
				ep[i][j][k]+=ep[i][j][k+1];
				ep[i][j][k]%=mod;
			}
		}
	}
	llint Owa[301]={};
	for(i=0;i<n;i++){
		Owa[i+1]=Owa[i];
		if(S[i]=='0'){Owa[i+1]++;}
	}
	
	llint ans=1;
	static bool mta[305][305]={};
	for(i=1;i<n;i++){//文字数
		for(j=min(n,n+n-i-i);j>=n-i+1;j--){//前方の取る数
			int kou=n-j;//後方のそのままの数
			int s=i+j-n;//前方から取得する数
			//cerr<<"i="<<i<<"j="<<j<<endl;
			//cerr<<"L="<<s-dpI[j][s]<<"R="<<dpO[j][s]<<endl;
			for(k=s-dpI[j][s];k<=dpO[j][s];k++){//0取得数
				int zO=Owa[n]-Owa[n-kou]+k;
				int zI=i-zO;
				if(mta[zO][zI]){continue;}
				mta[zO][zI]=1;
				ans+=ep[zO][zI][kou];
				//cerr<<"kou="<<kou<<"k="<<k<<endl;
				//cerr<<"ep["<<zO<<"]["<<zI<<"]["<<kou<<"]="<<ep[zO][zI][kou]<<endl;
				ans%=mod;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}