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;

const int maxN = 305, mod = 998244353;

int n;
int f[maxN + 1][maxN + 1][maxN + 1], g[maxN + 1][maxN + 1][maxN + 1];
bool res[maxN + 1][maxN + 1][maxN + 1];
char s[maxN + 1];

inline void chkmx(int &x, int y) { x = x > y ? x : y; }

inline void update(int &x, int y) { x = x + y >= mod ? x + y - mod : x + y; }

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);

	f[n][0][0] = 1;
	for(int i = n; i >= 1; i--)
		for(int j = 0; j <= n; j++)
			for(int k = 0; k <= n - j; k++)
			{
				if(!f[i][j][k]) continue;
				int t = f[i][j][k];
				update(f[i - 1][j][k], t);
				if(s[i] == '0') update(f[i][j][k + 1], t);
				else update(f[i][j + 1][k], t);
			}
	
	memset(g, -1, sizeof(g));
	g[0][0][0] = 0;
	for(int i = 0; i < n; i++)
		for(int j = 0; j <= i / 2; j++)
			for(int k = 0; k <= i / 2 - j; k++)
			{
				if(g[i][j][k] == -1) continue;
				int t = g[i][j][k];
				if(s[i + 1] == '0' && t) chkmx(g[i + 1][j + 1][k], t - 1);
				if(s[i + 1] == '1' && t) chkmx(g[i + 1][j][k + 1], t - 1);
				if(i + 2 <= n)
				{
					if(s[i + 1] == '0' || s[i + 2] == '0') chkmx(g[i + 2][j + 1][k], t);
					if(s[i + 1] == '1' || s[i + 2] == '1') chkmx(g[i + 2][j][k + 1], t);
					chkmx(g[i + 2][j][k], t + 1);
				}
			}
	
	int ans = mod - 1;
	for(int i = 0; i <= n; i++)
		for(int j = n; j >= 0; j--)
			for(int k = n - j; k >= 0; k--)
			{
				res[i][j][k] = (g[i][j][k] != -1);
				if(i) res[i][j][k] |= res[i - 1][j][k];
				res[i][j][k] |= (res[i][j + 1][k] | res[i][j][k + 1]);
				if(res[i][j][k]) update(ans, f[i][j][k]);
			}
	
	printf("%d\n", ans);
	return 0;
}