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;
typedef long long ll;
const int maxn=305;
const int mod=998244353;
int n,s0[maxn],s1[maxn],mx[maxn][maxn];
char s[maxn];
ll f[maxn][maxn][maxn];
inline void chkmax(int &a,int b) { a=(a>b)?a:b; }
int main()
{
	scanf("%s",s+1); n=strlen(s+1);
	for(int i=n;i;i--) s0[i]=s0[i+1]+(s[i]=='0'),s1[i]=s1[i+1]+(s[i]=='1');
	f[0][0][n+1]=1;
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=n+1;k;k--)
				if(f[i][j][k])
				{
					(f[i+1][j+1][k-((k>1)?s[k-1]=='0':0)]+=f[i][j][k])%=mod;
					(f[i+1][j][k-((k>1)?s[k-1]=='1':0)]+=f[i][j][k])%=mod;
				}
	for(int i=0;i<=n;i++)
		for(int j=0;j<=i;j++)
			for(int k=1;k<=n+1;k++) (f[i][j][k]+=f[i][j][k-1])%=mod;
	mx[s0[1]][s1[1]]=1;
	ll ans=0;
	for(int i=s0[1];i>=0;i--)
		for(int j=s1[1];j>=0;j--)
		{
			int k=mx[i][j];
			if(k<n)
			{
				if((s[k]=='0' || s[k+1]=='0') && i) chkmax(mx[i-1][j],k+2);
				if((s[k]=='1' || s[k+1]=='1') && j) chkmax(mx[i][j-1],k+2);
			}
			if(i && (k>n || i>s0[k+1])) chkmax(mx[i-1][j],min(k+1,n+1));
			if(j && (k>n || j>s1[k+1])) chkmax(mx[i][j-1],min(k+1,n+1));
			if(mx[i][j] && i+j>0) (ans+=f[i+j][i][mx[i][j]])%=mod;
		}
	printf("%lld\n",ans);
	return 0;
}