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<cstdio>
#include<cstring>
using namespace std;
#define N 305
const int mod=998244353;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
int dp[N][N][N],n,ans;
bool ok[N][N][N];
char s[N];
#define ck(x) (x>=mod?x-mod:x)
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=0;i<n;++i){
		ok[i][0][0]=true;
		for(int j=0;j<=i;++j){
			for(int k=0;k+j<=i;++k){
				if(!ok[i][j][k])continue;
				if(s[i+1]=='0'||s[i+2]=='0')ok[i+2][j+1][k]=true;
				if(s[i+1]=='1'||s[i+2]=='1')ok[i+2][j][k+1]=true;
				if(j|k)ok[i+1][j][k]=true;
				if(s[i+1]=='0'&&k)ok[i+1][j+1][k-1]=true;
				if(s[i+1]=='1'&&j)ok[i+1][j-1][k+1]=true;
			}
		}
	}
	dp[n][0][0]=1;
	for(int i=n;i>=1;--i){
		for(int j=0;j<=i;++j){
			for(int k=0;k+j<=i;++k){
				const int t=dp[i][j][k];
				if(!t)continue;
				dp[i-1][j][k]=ck(dp[i-1][j][k]+t);
				if(s[i]=='0')dp[i][j][k+1]=ck(dp[i][j][k+1]+t);
				else dp[i][j+1][k]=ck(dp[i][j+1][k]+t);
			}
		}
	}
	for(int i=0;i<=n;++i){
		for(int j=0;j<=i;++j){
			for(int k=0;k+j<=i;++k){
				if(ok[i][j][k])ans=ck(ans+dp[i][j][k]);
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}