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>
using namespace std;
const int mod=998244353;
char s[333];
int n,suf0[333],suf1[333],arr[333],mx[333][333],num[333][333][333],ans;
bool dp[333][333][333];
void upd(int &x,int y)
{
	if (x<y) x=y;
}
void add(int &x,int y)
{
	x+=y;
	if (x>=mod) x-=mod;
}
int main()
{
	scanf("%s",s);n=strlen(s);
	for (int i=1;i<=n;i++) arr[i]=s[i-1]-'0';
	for (int i=n;i>=1;i--)
	{
		suf0[i]=suf0[i+1]+(arr[i]==0);
		suf1[i]=suf1[i+1]+(arr[i]==1);
	} 
	dp[0][0][1]=1;
	for (int k=1;k<=n+1;k++)
	{
		for (int i=n;i>=0;i--)
		{
			for (int j=n;j>=0;j--)
			{
				if (!dp[i][j][k]) continue;
				if (arr[k]==1 || arr[k+1]==1) dp[i][j+1][k+2]=1;
				if (arr[k]==0 || arr[k+1]==0) dp[i+1][j][k+2]=1;
				dp[i][j][k+1]=1;
				if (arr[k]==1 && i) dp[i-1][j+1][k+1]=1;
				if (arr[k]==0 && j) dp[i+1][j-1][k+1]=1;
				if (i) dp[i-1][j][k]=1;
				if (j) dp[i][j-1][k]=1;
			}
		}
	}
	memset(mx,-1,sizeof(mx));
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			for (int k=1;k<=n+1;k++)
			{
				if (dp[i][j][k])
				{
					upd(mx[i+suf0[k]][j+suf1[k]],k);
				}
			}
		}
	}
	num[0][0][n]=1;
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			add(num[i+1][j][0],num[i][j][0]);
			add(num[i][j+1][0],num[i][j][0]);
			for (int k=1;k<=n;k++)
			{
				if (arr[k])
				{
					add(num[i+1][j][k],num[i][j][k]);
					add(num[i][j+1][k-1],num[i][j][k]);
				}
				else
				{
					add(num[i+1][j][k-1],num[i][j][k]);
					add(num[i][j+1][k],num[i][j][k]);
				}
			}
		}
	}
	for (int i=0;i<=n;i++)
	{
		for (int j=0;j<=n;j++)
		{
			if (!i && !j) continue;
			for (int k=0;k<=n;k++)
			{
				if (k<mx[i][j]) 
				{
					if (num[i][j][k]) 
					{
						add(ans,num[i][j][k]);
					}
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}