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 M=998244353;
int i,n,f[305][305][305],dp[305][305][305],s0[305],s1[305],j,k;
int mx[305][305],C[305][305];
char c[1005];
void dfs(int i,int j,int k)
{
	if(f[i][j][k])
		return;
	f[i][j][k]=1;
	mx[j+s0[i]][k+s1[i]]=max(mx[j+s0[i]][k+s1[i]],i);
	if(i+1<=n)
	{
		if(c[i]=='0'||c[i+1]=='0')
			dfs(i+2,j+1,k);
		if(c[i]=='1'||c[i+1]=='1')
			dfs(i+2,j,k+1);
	}
	if(j+k>=2&&j)
		dfs(i,j-1,k);
	if(j+k>=2&&k)
		dfs(i,j,k-1);
	if(j+k>=1&&i<=n)
	{
		dfs(i+1,j,k);
		if(c[i]=='0')
			if(k)
				dfs(i+1,j+1,k-1);
		if(c[i]=='1')
			if(j)
				dfs(i+1,j-1,k+1);
	}
}
int dfs2(int i,int j,int k)
{
	if(i>n)
		return C[j+k][j];
	if(dp[i][j][k]!=-1)
		return dp[i][j][k];
	int s=0;
	if(c[i]=='0')
		if(k)
			s+=dfs2(i,j,k-1);
	if(c[i]=='1')
		if(j)
			s+=dfs2(i,j-1,k);
	s+=dfs2(i+1,j,k);
	return dp[i][j][k]=s%M;
}
int main()
{
	scanf("%s",c+1);
	n=strlen(c+1);
	for(i=n;i>=1;--i)
	{
		s0[i]=s0[i+1]+(c[i]=='0');
		s1[i]=s1[i+1]+(c[i]=='1');
	}
	for(i=0;i<=n;++i)
	{
		C[i][0]=C[i][i]=1;
		for(j=1;j<i;++j)
			C[i][j]=(C[i-1][j]+C[i-1][j-1])%M;
	}
	memset(dp,-1,sizeof(dp));
	dfs(1,0,0);
	long long ans=0;
	for(i=0;i<=n;++i)
		for(j=0;j<=n;++j)
			if(mx[i][j])
				ans+=dfs2(mx[i][j],i-s0[mx[i][j]],j-s1[mx[i][j]]);
	cout<<(ans%M+M)%M;
}