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>
typedef int LL;
const LL mod=998244353,maxn=3e2+9;
LL n;
LL f[maxn][maxn][maxn],g[maxn][maxn][maxn],is[maxn][maxn][maxn];
char s[maxn];
LL add(LL x,LL y){ return x+=y,x>=mod?x-mod:x; }
LL mul(LL x,LL y){ return 1ll*x*y%mod; }
void chkmax(LL &x,LL y){ x=std::max(x,y); }
void chkmin(LL &x,LL y){ x=std::min(x,y); }
int main(){
	scanf(" %s",s+1);
	//f[n][0][0]=1;
	n=strlen(s+1);
	f[n][0][0]=1;
	for(LL i=n;i>=1;--i){
		for(LL j=0;j<=n;++j){
			for(LL k=0;k<=n;++k){
				f[i-1][j][k]=add(f[i-1][j][k],f[i][j][k]);
				if(s[i]=='0'){
					f[i][j][k+1]=add(f[i][j][k+1],f[i][j][k]);
				}else{
					f[i][j+1][k]=add(f[i][j+1][k],f[i][j][k]);
				}
				//if(i==3 && !j && !k) printf("%d,%d\n",f[n][0][0],f[i][j][k]);
			}
		}
	}
	memset(g,-1,sizeof(g));
	g[0][0][0]=0;
	for(LL i=0;i<=n;++i){
		for(LL j=0;j<=i;++j){
			for(LL k=0;k<=i;++k){
				LL tmp(g[i][j][k]);
				if(tmp==-1) continue;
				if(i+1<=n && tmp){
					if(s[i+1]=='0') chkmax(g[i+1][j+1][k],tmp-1);
					if(s[i+1]=='1') chkmax(g[i+1][j][k+1],tmp-1);
				}
				if(i+2<=n){
					if(s[i+1]=='0' || s[i+2]=='0') chkmax(g[i+2][j+1][k],tmp);
					if(s[i+1]=='1' || s[i+2]=='1') chkmax(g[i+2][j][k+1],tmp);
					chkmax(g[i+2][j][k],tmp+1);
				}
			}
		}
	}
	LL ret(0);
	for(LL i=0;i<=n;++i){
		for(LL j=i;j>=0;--j){
			for(LL k=i;k>=0;--k){
				is[i][j][k]=(g[i][j][k]!=-1);
				if(i) is[i][j][k]|=is[i-1][j][k];
				is[i][j][k]|=is[i][j+1][k];
				is[i][j][k]|=is[i][j][k+1];
			}
		}
	}
	for(LL i=0;i<=n;++i){
		for(LL j=0;j<=i;++j){
			for(LL k=0;k<=i;++k){
				if(n-i+j+k && is[i][j][k]){
					ret=add(ret,f[i][j][k]);
					//printf("%d,%d,%d\n",i,j,k);
				}
			}
		}
	}
	printf("%d\n",ret);
	return 0;
}