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>

const int N = 305, djq = 998244353;

int n, f[N][N][N], ans;
char s[N];
bool is[N][N][N], can[N][N][N];

int main()
{
	scanf("%s", s + 1); n = strlen(s + 1);
	f[0][0][0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; j + k <= i; k++)
			{
				f[i + 1][j + 1][k] = (f[i + 1][j + 1][k] + f[i][j][k]) % djq;
				f[i + 1][j][k + s[n - j] - '0'] =
					(f[i + 1][j][k + s[n - j] - '0'] + f[i][j][k]) % djq;
			}
	is[0][0][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; k <= i; k++)
			{
				if (i > 1)
				{
					if (j && (s[i] == '0' || s[i - 1] == '0'))
						is[i][j][k] |= is[i - 2][j - 1][k];
					if (k && (s[i] == '1' || s[i - 1] == '1'))
						is[i][j][k] |= is[i - 2][j][k - 1];
				}
				if (s[i] == '0' && j) is[i][j][k] |= is[i - 1][j - 1][k + 1];
				if (s[i] == '1' && k) is[i][j][k] |= is[i - 1][j + 1][k - 1];
				is[i][j][k] |= is[i - 1][j][k];
			}
	for (int i = 1; i <= n; i++) is[i][0][0] = 0;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; j + k <= i; k++)
				can[i][j][k] = is[n - j][k][i - j - k] ||
					(j && can[i][j - 1][k + (s[n - j + 1] == '0')]);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; j + k <= i; k++)
				if (can[i][j][k]) ans = (ans + f[i][j][k]) % djq;
	return std::cout << ans << std::endl, 0;
}