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;

const int maxn=305;
const int mod=998244353;
int n,ans;
char s[maxn];
bool f[maxn][maxn][maxn];
int g[maxn][maxn][maxn],suf[maxn];

void Add(int &a,int b){
	a+=b;
	if(a>=mod)a-=mod;
}

int main(){
	scanf("%s",s);n=strlen(s);
	f[0][0][0]=true;
	for(int i=0;i<n;i++)for(int j=n;j>=0;j--)for(int k=n;k>=0;k--)if(f[i][j][k]){
		if(i+1<n){
			if(s[i]=='0'||s[i+1]=='0')f[i+2][j+1][k]=true;
			if(s[i]=='1'||s[i+1]=='1')f[i+2][j][k+1]=true;
		}
		if(j+k>=2){
			if(j)f[i][j-1][k]=true;
			if(k)f[i][j][k-1]=true;
		}
		if(j+k>=1){
			f[i+1][j][k]=true;
			if(s[i]=='0'&&k)f[i+1][j+1][k-1]=true;
			if(s[i]=='1'&&j)f[i+1][j-1][k+1]=true;
		}
	}
	g[0][0][n]=1;
	for(int j=0;j<=n;j++)for(int k=0;k<=n;k++)for(int i=n;i>=0;i--)if(g[j][k][i]){
		Add(g[j+1][k][i-(i>0&&s[i-1]=='0')],g[j][k][i]);
		Add(g[j][k+1][i-(i>0&&s[i-1]=='1')],g[j][k][i]);
	}
	suf[n]=0;
	for(int i=n-1;i>=0;i--)suf[i]=suf[i+1]+(s[i]=='1');
	for(int j=0;j<=n;j++)for(int k=0;k<=n;k++){
		int mx=-1;
		for(int i=0;i<=n;i++)
			if(j-(n-i-suf[i])>=0&&k-suf[i]>=0&&f[i][j-(n-i-suf[i])][k-suf[i]])mx=i;
		for(int i=0;i<=mx;i++)Add(ans,g[j][k][i]);
	}
	printf("%d\n",ans);
	return 0;
}