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>
const int mod=998244353;
#define Rint register int
#define C(n,m) (n<m?0:1ll*fac[n]*invfac[n-m]%mod*invfac[m]%mod)
using namespace std;
int T,n,m,p,k;
bool f[310][310][310];
int dp[310][310][310],C[610][610],ans=0;
char s[310];
int main(){
	scanf("%s",s),n=strlen(s);
	for(int i=0;i<=2*n;i++){
		C[i][0]=1;
		for(int j=1;j<=i;j++) C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod; 
	} 
	for(int j=0;j<=n;j++) for(int k=0;k<=n;k++) dp[n][j][k]=C[j+k][j];
	for(int i=n-1;i>=0;i--) for(int j=0;j<=i;j++) for(int k=0;k<=i;k++){
		dp[i][j][k]=dp[i+1][j][k];
		if(s[i]=='0'&&k) dp[i][j][k]=(dp[i][j][k]+dp[i][j][k-1])%mod;
		if(s[i]=='1'&&j) dp[i][j][k]=(dp[i][j][k]+dp[i][j-1][k])%mod;
	}
	f[0][0][0]=true;
	for(int i=0;i<=n;i++){
		for(int j=i;j>=0;j--){
			for(int k=i;k>=0;k--){
				if(j&&j+k>=2) f[i][j-1][k]|=f[i][j][k];
				if(k&&j+k>=2) f[i][j][k-1]|=f[i][j][k];
				if(i+1<=n){
					if(j&&s[i]=='1') f[i+1][j-1][k+1]|=f[i][j][k];
					if(k&&s[i]=='0') f[i+1][j+1][k-1]|=f[i][j][k];
					if(j+k) f[i+1][j][k]|=f[i][j][k];
				}
				if(i+2<=n){
					if(s[i]=='0'||s[i+1]=='0') f[i+2][j+1][k]|=f[i][j][k];
					if(s[i]=='1'||s[i+1]=='1') f[i+2][j][k+1]|=f[i][j][k];
				}
			}
		}
	}
	for(int i=n;i>=0;i--){
		for(int j=i;j>=0;j--){
			for(int k=i;k>=0;k--){
				if(!f[i][j][k]) continue;
				ans=(ans+dp[i][j][k])%mod;
				int cnt[2]={};
				for(int l=i-1;l>=0;l--){
					cnt[s[l]-'0']++;
					if(j<cnt[0]||k<cnt[1]) break;
					f[l][j-cnt[0]][k-cnt[1]] = false;
				}
			}
		}
	}
	printf("%d\n",ans);
}