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:
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(int x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(int x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const int P = 998244353;
int add(int a, int b)
{
	return a + b >= P ? a + b - P : a + b;
}
void inc(int &a, int b)
{
	a = add(a, b);
}
int mul(int a, int b)
{
	return 1LL * a * b % P;
}
const int N = 300 + 10;
char s[N];
int n, dp[N][N][N], f[N][N][N], valid[N][N][N];
void upd(int &x, int y)
{
	x = max(x, y);
}
int main()
{
	scanf("%s", s + 1), n = strlen(s + 1), dp[n][0][0] = 1;
	for (int i = n; i >= 1; --i)
		for (int j = 0; j + (n - i) <= n - 1; ++j)
			for (int k = 0; j + k + (n - i) <= n - 1; ++k)
			{
				inc(dp[i - 1][j][k], dp[i][j][k]);
				if (s[i] == '0')
					inc(dp[i][j][k + 1], dp[i][j][k]);
				else
					inc(dp[i][j + 1][k], dp[i][j][k]);
			}
	memset(f, -1, sizeof f);
	f[0][0][0] = 0;
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j <= (i >> 1); ++j)
			for (int k = 0; j + k <= (i >> 1); ++k) if (f[i][j][k] != -1)
			{
				int tmp = f[i][j][k];
				if (i + 1 <= n && tmp != 0)
				{
					if (s[i + 1] == '0')
						upd(f[i + 1][j + 1][k], tmp - 1);
					else
						upd(f[i + 1][j][k + 1], tmp - 1);	
				}
				if (i + 2 <= n)
				{
					if (s[i + 1] == '0' || s[i + 2] == '0')
						upd(f[i + 2][j + 1][k], tmp);
					if (s[i + 1] == '1' || s[i + 2] == '1')
						upd(f[i + 2][j][k + 1], tmp);
					upd(f[i + 2][j][k], tmp + 1);
				}
			}
	for (int i = 0; i <= n; ++i)
		for (int j = n; j >= 0; --j)
			for (int k = n; k >= 0; --k)
			{
				valid[i][j][k] = (f[i][j][k] != -1);
				if (i)
					valid[i][j][k] |= valid[i - 1][j][k];
				valid[i][j][k] |= valid[i][j][k + 1];
				valid[i][j][k] |= valid[i][j][k + 1];
			}
	int ans = 0;
	for (int i = 0; i <= n; ++i)
		for (int j = 0; j + (n - i) <= n; ++j)
			for (int k = 0; j + k + (n - i) <= n; ++k)
				if (valid[i][j][k] && (n - i) + j + k != 0)
					inc(ans, dp[i][j][k]);
	write(ans, '\n');
	return 0;
}