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>
#define ll long long
using namespace std;
const int p=998244353;
int n,m,i,j,k,l,ans,sz0,sz1,flag,v[303][303][303],f[303][303][303];
char s[303];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	//if(n>100)return puts("0"),0;
	f[n+1][0][0]=1;
	for(i=n+1;i>=1;i--){
		for(j=0;j<=n;j++)
		 for(k=0;k<=n-j;k++)if(f[i][j][k]){
		 	if(i==1||s[i-1]!='0')(f[i][j+1][k]+=f[i][j][k])%=p;
		 	if(i==1||s[i-1]!='1')(f[i][j][k+1]+=f[i][j][k])%=p;
		 	if(i>1){
		 		/*if(s[i-1]=='0')(f[i-1][j][k]+=f[i][j][k])%=p;
		 		if(s[i-1]=='1')(f[i-1][j])*/
		 		(f[i-1][j][k]+=f[i][j][k])%=p;
			 }
		 }
	}
	v[0][0][0]=1;
	for(i=0;i<=n;i++)
	 for(j=n;j>=0;j--)
	  for(k=n-j;k>=0;k--)if(v[i][j][k]){
	  	if(j+k>=2){
	  		if(j)v[i][j-1][k]=1;
	  		if(k)v[i][j][k-1]=1;
		  }
		if(i<n){
			if(j+k>0)v[i+1][j][k]=1;
			if(s[i+1]=='0'){
				if(k)v[i+1][j+1][k-1]=1;
			}
			if(s[i+1]=='1'){
				if(j)v[i+1][j-1][k+1]=1;
			}
		}
		if(i+1<n){
			if(s[i+1]=='0'||s[i+2]=='0')v[i+2][j+1][k]=1;
			if(s[i+1]=='1'||s[i+2]=='1')v[i+2][j][k+1]=1;
		}
	  }
	  for(i=n;i;i--)
	   for(j=0;j<=n;j++)
	    for(k=0;k<=n-j;k++)if(v[i][j][k]){
	    	if(s[i]=='0'&&j)v[i-1][j-1][k]=1;
	    	if(s[i]=='1'&&k)v[i-1][j][k-1]=1;
		}
	  for(i=0;i<=n;i++)
	   for(j=0;j<=n;j++)
	    for(k=0;k<=n-j;k++)if(v[i][j][k]){
	    	//printf("%d %d %d %d\n",i,j,k,f[i+1][j][k]);
	    	ans=(ans+f[i+1][j][k])%p;
	    	/*flag=0;sz0=sz1=0;
	    	for(l=i-1;l<=n;l++){
	    		if(v[l][j+sz0][k+sz1]){
	    			flag=1;break;
				}
				if(s[l+1]=='0')sz0++;
				 else sz1++;
			}
			if(flag){
			  ans=(ans+f[i][j][k])%p;
			  //printf("%d %d %d %d\n",i,j,k,f[i][j][k]);
		   }*/
		}
	printf("%d",ans);
}
/*

*/