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<iostream>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define all(x) x.begin(),x.end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define mod 998244353
#define pl(a,b) a=(a+b)%mod;
#define N 310

string s;
ll n;
ll f[N][N][N];
void calcf(){
	rep(i,N)rep(x,N)rep(y,N)f[i][x][y]=0;
	f[0][0][0]=1;
	for(ll i=0;i<=n;i++)for(ll x=0;x<=n;x++)for(ll y=0;y<=n;y++){
		if(i+x+y>n)continue;
		if(i+1<=n){
			pl(f[i+1][x][y],f[i][x][y]);
			if(s[n-1-i]=='0')pl(f[i][x][y+1],f[i][x][y]);
			if(s[n-1-i]=='1')pl(f[i][x+1][y],f[i][x][y]);
		}
		else{
			pl(f[i][x+1][y],f[i][x][y]);
			pl(f[i][x][y+1],f[i][x][y]);
		}
	}
}

bool dp[N][N][N];
void calcdp(){
	ll ans=-1;
	rep(i,N)rep(x,N)rep(y,N)dp[i][x][y]=0;
	dp[0][0][0]=1;
	for(ll i=0;i<=n;i++)for(ll x=0;x<=n;x++)for(ll y=0;y<=n;y++){
		if(n-i+x+y>n)continue;
		if(dp[i][x][y]==0)continue;
		pl(ans,f[n-i][x][y]);
		if(x-1>=0)dp[i][x-1][y]=1;
		if(y-1>=0)dp[i][x][y-1]=1;
		if(i+1<=n){
			dp[i+1][x][y]=1;
			if(s[i]=='0'&&y-1>=0)dp[i+1][x+1][y-1]=1;
			if(s[i]=='1'&&x-1>=0)dp[i+1][x-1][y+1]=1;
		}
		if(i+2<=n){
			rep(r,2){
				bool th=0;
				rep(e,2)if(s[i+e]=='0'+r)th=1;
				if(th){
					if(r==0)dp[i+2][x+1][y]=1;
					if(r==1)dp[i+2][x][y+1]=1;
				}
			}
		}
	}
	cout<<ans<<endl;
}

int main(){
	cin>>s;
	n=s.size();
	calcf();
	calcdp();
}