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 ll mod=998244353;
const int N=605;
int n;
string s;
ll dp[N][N];//number maximum number of 1 that can be picked if j 0s is picked among the first i
ll c[N][N];
ll dp2[3][N][N];
int main(){
	ios::sync_with_stdio(false);
	cin >> s;n=s.size();s='?'+s;
	if(n==1){
		cout << "1\n";
		return 0;
	}
	for(int i=0; i<=2*n ;i++){
		for(int j=0; j<=2*n ;j++){
			dp[i][j]=-1e9;
			dp2[0][i][j]=-1e9;
			dp2[1][i][j]=-1e9;
			dp2[2][i][j]=-1e9;
		}
		dp[i][0]=0;
		c[i][0]=1;
		for(int j=1; j<=i ;j++){
			c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
		}
	}
	dp2[0][0][0]=0;
	dp[0][0]=0;
	for(int i=1; i<=n ;i++){
		int c=i%3;
		int p=(c+2)%3;
		int q=(c+1)%3;
		for(int j=0; j<=i ;j++){
			for(int k=0; k<=i ;k++){
				dp2[c][j][k]=-1e9;
			}
		}
		for(int j=0; j<=i ;j++){
			for(int k=0; k<=i ;k++){
				if(i>=2 && j>=1) dp2[c][j][k]=max(dp2[c][j][k],dp2[q][j-1][k]);//aa->power
				if(i>=2 && (s[i-1]=='1' || s[i]=='1')) dp2[c][j][k]=max(dp2[c][j][k],dp2[q][j][k]+1);//ab,ba->void
				if(i>=2 && (s[i-1]=='0' || s[i]=='0') && k>=1) dp2[c][j][k]=max(dp2[c][j][k],dp2[q][j][k-1]);//ab,ba->void
				if(s[i]=='1') dp2[c][j][k]=max(dp2[c][j][k],dp2[p][j+1][k]+1);
				if(s[i]=='0' && k>=1) dp2[c][j][k]=max(dp2[c][j][k],dp2[p][j+1][k-1]);
				dp[i][k]=max(dp[i][k],dp2[c][j][k]);
			}
		}
	}
	for(int i=1; i<=n ;i++){
		for(int j=0; j<=i-2 ;j++){
			bool hv0=false;
			bool hv1=false;
			for(int k=j+1; k<=i ;k++){
				if(s[k]=='0') hv0=true;
				if(s[k]=='1') hv1=true;
			}
			for(int k=0; k<=i ;k++){
				if(hv1) dp[i][k]=max(dp[i][k],dp[j][k]+1);
				if(hv0 && k!=0) dp[i][k]=max(dp[i][k],dp[j][k-1]);
			}
		}
	}
	ll ans=0;
	for(int i=n; i>=1 ;i--){
		int c0=0,c1=0;
		for(int j=n; j>=i ;j--){
			if(s[j]=='0') c1++;
			else c0++;
		}
		for(int j=0; j<=i ;j++){
			for(int k=0; k<=dp[i][j] ;k++){
				if(c0==0 && j!=0) continue;
				if(c1==0 && k!=0) continue;
				ll w1=1,w2=1;
				if(j!=0) w1=c[j+c0-1][c0-1];
				if(k!=0) w2=c[k+c1-1][c1-1];
				ans=(ans+w1*w2)%mod;
			}
		}
	}
	cout << ans << '\n';
}