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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char s[305];
int n,dp[305][305][305],ans=0,vis[305][305],sum[2][305],add[2][305][305][305];
int sump[305][305][305];
int cr[305][305][305];
const int mod=998244353;
int M(int x){return x>=mod?x-mod:x;}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++)
	{
		sum[0][i]=sum[0][i-1];
		sum[1][i]=sum[1][i-1];
		if(s[i]=='0')sum[0][i]++;
		else sum[1][i]++;
	}
	for(int i=0;i<=n;i++)for(int j=0;j<=i;j++)for(int k=0;k<=i-j;k++)cr[i][j][k]=-2;
	cr[0][0][0]=0;
	vis[sum[0][n]][sum[1][n]]=1;
	//w/b
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=i;j++)
		{
			for(int k=0;k<=i-j;k++)
			{
				if(cr[i][j][k]==-2)continue;
				if(j+k&&cr[i][j][k]>=0)vis[j+sum[0][n]-sum[0][i]][k+sum[1][n]-sum[1][i]]=i+1;
				if(cr[i][j][k]==-1)cr[i+1][j][k]=max(cr[i+1][j][k],0);
				else cr[i+1][j][k]=max(cr[i+1][j][k],cr[i][j][k]+1);
				if(i<n&&cr[i][j][k]>-1)
				{
					if(s[i+1]=='0')cr[i+1][j+1][k]=max(cr[i+1][j+1][k],max(-1,cr[i][j][k]-1-(cr[i][j][k]%2==0)));
					else cr[i+1][j][k+1]=max(cr[i+1][j][k+1],max(-1,cr[i][j][k]-1-(cr[i][j][k]%2==0)));
					if(cr[i][j][k]>0&&cr[i][j][k]%2==0&&i<n-1)
					{
						if(s[i+1]=='0')cr[i+2][j+1][k]=max(cr[i+2][j+1][k],cr[i][j][k]);
						else cr[i+2][j][k+1]=max(cr[i+2][j][k+1],cr[i][j][k]);
					}
				}
			}
		}
	}
	dp[0][0][0]=1;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			for(int k=0;k<=n;k++)
			{
				if(j)add[0][i][j][k]=M(add[0][i][j][k]+add[0][i][j-1][k]);
				if(k)add[1][i][j][k]=M(add[1][i][j][k]+add[1][i][j][k-1]);
				dp[i][j][k]=M(dp[i][j][k]+M(add[0][i][j][k]+add[1][i][j][k]));
				sump[i][j][k]=M(sump[i][j][k]+dp[i][j][k]);
				sump[i][j+1][k]=M(sump[i][j+1][k]+sump[i][j][k]);
				sump[i][j][k+1]=M(sump[i][j][k+1]+sump[i][j][k]);
				if(i==n)continue;
				if(s[n-i]=='0')add[1][i+1][j][k]=M(add[1][i+1][j][k]+dp[i][j][k]);
				else add[0][i+1][j][k]=M(add[0][i+1][j][k]+dp[i][j][k]);
			}
		}
	}
	//printf("@%d\n",dp[2][0][0]);
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(i==0&&j==0)continue;
			if(!vis[i][j])continue;
			//printf("%d %d %d %d\n",i,j,vis[i][j],sump[n-vis[i][j]+1][i-sum[0][n]+sum[0][vis[i][j]-1]][j-sum[1][n]+sum[1][vis[i][j]-1]]);
			ans=M(ans+sump[n-vis[i][j]+1][i-sum[0][n]+sum[0][vis[i][j]-1]][j-sum[1][n]+sum[1][vis[i][j]-1]]);
		}
	}
	printf("%d\n",ans);
	return 0;
}