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 cs const
#define pb push_back
using namespace std;
void ckmx(int &a, int b){ if(a < b) a = b; }
cs int Mod = 998244353;
int add(int a, int b){ return a + b >= Mod ? a + b - Mod : a + b; }
int dec(int a, int b){ return a - b < 0 ? a - b + Mod : a - b; }
void Add(int &a, int b){ a = add(a,b); }
void Dec(int &a, int b){ a = dec(a,b); }
cs int N = 305;
int n; char S[N];
int dp[N][N][N], ok[N][N][N];
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%s",S+1); n=strlen(S+1);
	dp[n][0][0] = 1;
	for(int i=n; i>=1; i--)
	for(int j=0; j<=i; j++)
	for(int k=0,coe; j+k<=i; k++)
	if(coe=dp[i][j][k]){	
		Add(dp[i-1][j][k],coe);
		if(S[i]=='0')Add(dp[i][j][k+1],coe);
		if(S[i]=='1')Add(dp[i][j+1][k],coe);
	}
	memset(ok,-1,sizeof(ok));
	ok[0][0][0] = 0;
	for(int i=0; i<n; i++)
	for(int j=0; j<=i; j++)
	for(int k=0,coe; j+k<=i; k++)
	if(~(coe=ok[i][j][k])){
		ckmx(ok[i+1][j][k],coe);
		if(S[i+1]=='0'&&coe)ckmx(ok[i+1][j+1][k],coe-1);
		if(S[i+1]=='1'&&coe)ckmx(ok[i+1][j][k+1],coe-1);
		if(i+1<n){
			ckmx(ok[i+2][j][k],coe+1);
			if(S[i+1]=='0'||S[i+2]=='0')ckmx(ok[i+2][j+1][k],coe);
			if(S[i+1]=='1'||S[i+2]=='1')ckmx(ok[i+2][j][k+1],coe);
		}
	} int ans = 0;
	for(int i=0; i<=n; i++)
	for(int j=0; j<=i; j++)
	for(int k=0,t; j+k<=i; k++)
	if(ok[i][j][k]>=0 && n-i+j+k>0)
	Add(ans,dp[i][j][k]);
	cout << ans; return 0;
}