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 <stdio.h>
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 305;
const int MOD = 998244353;

int n,ans;
int f[MAXN][MAXN][MAXN];
int g[MAXN][MAXN][MAXN];

char s[MAXN];

bool G(int T,int j,int R0,int R1)
{
	int r[2] = {R0,R1};
	if (R0 + R1 > n - j + 1)
		return 0;
	if (j > n)
		return 1;
	if (!T)
		return 0;
	if (j == n)
		return 1;
	int &res = g[T][j][R0];
	if (~res)
		return res;
	res = G(T - 1,j + 1,r[0],r[1]);
	if (r[s[j] - '0'])
	{
		r[s[j] - '0']--;
		res |= G(T - 1,j + 2,r[0],r[1]);
		r[s[j] - '0']++;
		r[s[j] - '0']--;
		r[(s[j + 1] - '0') ^ 1]++;
		res |= G(T - 1,j + 1,r[0],r[1]);
		r[s[j] - '0']++;
		r[(s[j + 1] - '0') ^ 1]--;
	}
	if (r[s[j + 1] - '0'])
	{
		r[s[j + 1] - '0']--;
		res |= G(T - 1,j + 2,r[0],r[1]);
		r[s[j + 1] - '0']++;
	}
	return res;
}

int main()
{
	memset(g,-1,sizeof(g));
	scanf("%s",s + 1);
	n = strlen(s + 1);
	int cnt[2] = {0};
	for (int i = 1;i <= n;i++)
		cnt[s[i] - '0']++;
	reverse(s + 1,s + n + 1);
	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])
				{
					if (s[j + 1] == '0')
					{
						(f[i + 1][j + 1][k + 1] += f[i][j][k]) %= MOD;
						(f[i + 1][j][k] += f[i][j][k]) %= MOD;
					}
					else
					{
						(f[i + 1][j][k + 1] += f[i][j][k]) %= MOD;
						(f[i + 1][j + 1][k] += f[i][j][k]) %= MOD;
					}
				}
	for (int i = 1;i <= n;i++)
	{
		int c[2] = {0};
		for (int j = 0;j <= i;j++)
		{
			if (j > 0)
				c[s[j] - '0']++;
			for (int k = 0;k <= i;k++)
			{
				if (!f[i][j][k])
					continue;
				if (G(n - i,j + 1,k - c[0],i - k - c[1]))
					(ans += f[i][j][k]) %= MOD;
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}