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 SIZE 305
#define MOD 998244353
using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

char S[SIZE];
int dp[SIZE][SIZE];
int C[SIZE][SIZE];
int r0[SIZE],r1[SIZE];

void make()
{
	for(int i=0;i<SIZE;i++)
	{
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;j++)
		{
			C[i][j]=C[i-1][j-1]+C[i-1][j];
			if(C[i][j]>=MOD) C[i][j]-=MOD;
		}
	}
}
int main()
{
	make();
	scanf("%s",&S);
	int n=strlen(S);
	//int n=300;
	//for(int i=0;i<n;i++) S[i]='0'+(i%2);
	for(int i=0;i<n;i++)
	{
		r0[i]=S[i]=='0';
		r1[i]=S[i]=='1';
		if(i>0)
		{
			r0[i]+=r0[i-1];
			r1[i]+=r1[i-1];
		}
	}
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(dp[i][j]==-1) continue;
			if(dp[i][j]>=n-1) dp[i][j]=dp[i+1][j]=dp[i][j+1]=n;
			else
			{
				int v=dp[i][j];
				if(S[v]!=S[v+1])
				{
					dp[i+1][j]=max(dp[i+1][j],v+2);
					dp[i][j+1]=max(dp[i][j+1],v+2);
				}
				else if(S[v]=='0')
				{
					dp[i+1][j]=max(dp[i+1][j],v+2);
					if(j+1<=r1[v]) dp[i][j+1]=max(dp[i][j+1],v+1);
				}
				else
				{
					dp[i][j+1]=max(dp[i][j+1],v+2);
					if(i+1<=r0[v]) dp[i+1][j]=max(dp[i+1][j],v+1);
				}
			}
		}
	}
	ll ret=MOD-1;
	for(int i=0;i<=r0[n-1];i++)
	{
		for(int j=0;j<=r1[n-1];j++)
		{
			if(dp[i][j]==-1) continue;
			int v=dp[i][j];
			int zero,one;
			int a,b;
			if(v==0)
			{
				zero=one=0;
				a=r0[n-1];
				b=r1[n-1];
			}
			else
			{
				zero=r0[v-1]-i,one=r1[v-1]-j;
				a=r0[n-1]-r0[v-1],b=r1[n-1]-r1[v-1];
			}
			int f=zero,s=one;
			if(b==0) f=0;
			if(a==0) s=0;
			for(int k=0;k<=f;k++)
			{
				for(int l=0;l<=s;l++)
				{
					ll w=C[zero+one-k-l][zero-k];
					if(b>0) w=w*(ll) C[k+b-1][b-1]%MOD;
					if(a>0) w=w*(ll) C[l+a-1][a-1]%MOD;
					ret+=w;
					if(ret>=MOD) ret-=MOD;
				}
			}
		}
	}
	printf("%lld\n",ret);
}