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 int long long
using namespace std;
const int N=3e2+5;
const int p=998244353;

int read()
{
	int s=0;
	char c=getchar(),lc='+';
	while (c<'0'||'9'<c) lc=c,c=getchar();
	while ('0'<=c&&c<='9') s=s*10+c-'0',c=getchar();
	return lc=='-'?-s:s;
}
void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x=-x;
	}
	if (x<10) putchar(x+'0');
	else
	{
		write(x/10);
		putchar(x%10+'0');
	}
}
void print(int x,char c='\n')
{
	write(x);
	putchar(c);
}
char a[N];
bool f[N][N][N];
int dp[N][N][N];
void add(int &x,int y)
{
	x+=y;
	if (x>=p) x-=p;
}

signed main()
{
	memset(f,0,sizeof(f));
	memset(dp,0,sizeof(dp));
	scanf("%s",a+1);
	int n=strlen(a+1),ans=0;
	f[0][0][0]=1;
	for (int i=0;i<n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++)
	if (f[i][j][k])
	{
		f[i+1][j][k]=1;
		if (a[i+1]=='0'||a[i+2]=='0') f[i+2][j+1][k]=1;
		if (a[i+1]=='1'||a[i+2]=='1') f[i+2][j][k+1]=1;
		if (a[i+1]=='0'&&k) f[i+1][j+1][k-1]=1;
		if (a[i+1]=='1'&&j) f[i+1][j-1][k+1]=1;
	}
//	for (int i=1;i<=n;i++){for (int j=0;j<=i;j++){for (int k=0;k<=i;k++)putchar(f[i][j][k]+'0');puts("");}puts("");}
	dp[n][0][0]=1;
	for (int i=n;i>=1;i--)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++)
	{
		add(dp[i-1][j][k],dp[i][j][k]);
		if (a[i]=='1') add(dp[i][j+1][k],dp[i][j][k]);
		if (a[i]=='0') add(dp[i][j][k+1],dp[i][j][k]);
	}
	for (int i=1;i<=n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++)
	add(ans,f[i][j][k]*dp[i][j][k]);
	print(ans);

	return 0;
}