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 MX = 301, md = 998244353;

char s[MX];
int dp[MX][MX][MX], f[MX][MX][MX];

void upd(int e0, int e1, int f0, int f1) {
	int& val = dp[e0][e1][f0];
	val = max(val, f1);
}

int main() {
	ignore = scanf("%s", s);
	
	int n = strlen(s);
	
	memset(dp, -1, sizeof dp);
	
	dp[0][0][0] = 0;
	for (int e0 = 0; e0 < MX; e0++)
		for (int e1 = 0; e1 < MX; e1++)
			for (int f0 = 0; f0 < MX; f0++) {
				if (dp[e0][e1][f0] == -1) continue;
				
				int f1 = dp[e0][e1][f0];
				
				// both free
				if (f0 + f1 >= 2) {
					if (f0 > 0) upd(e0 + 1, e1, f0 - 1, f1);
					if (f1 > 0) upd(e0, e1 + 1, f0, f1 - 1);
				}
				
				// both fixed
				if (e0 + e1 + f0 + f1 + 1 < n) {
					int x = s[e0 + e1 + f0 + f1] - '0';
					int y = s[e0 + e1 + f0 + f1 + 1] - '0';
					
					if (x != y) {
						upd(e0 + 1, e1, f0, f1 + 1);
						upd(e0, e1 + 1, f0 + 1, f1);
					}
					else if (x == 0) {
						upd(e0 + 1, e1, f0 + 1, f1);
					}
					else {
						upd(e0, e1 + 1, f0, f1 + 1);
					}
				}
				
				// one free, one fixed
				if (f0 + f1 > 0 && e0 + e1 + f0 + f1 < n) {
					int x = s[e0 + e1 + f0 + f1] - '0';
					
					if (x == 0) {
						upd(e0 + 1, e1, f0, f1);
						
						if (f1 > 0) upd(e0, e1 + 1, f0 + 1, f1 - 1);
					}
					else {
						upd(e0, e1 + 1, f0, f1);
						
						if (f0 > 0) upd(e0 + 1, e1, f0 - 1, f1 + 1);
					}
				}
			}
	
	int ans = 0;
	for (int e0 = 0; e0 < MX; e0++)
		for (int e1 = 0; e1 < MX; e1++) {
			int f0 = -1, f1 = -1;
			for (int x0 = 0; x0 < MX; x0++) {
				int x1 = dp[e0][e1][x0];
				if (x1 != -1 && x0 + x1 > f0 + f1) {
					f0 = x0;
					f1 = x1;
				}
			}
			
			if (f0 == -1) continue;
			
			int k = e0 + e1 + f0 + f1;
			
			f[k][f0][f1]++;
		}
	
	for (int i = 0; i < n; i++)
		for (int x = n; x >= 0; x--)
			for (int y = n; y >= 0; y--) {
				f[i + 1][x][y] += f[i][x][y];
				f[i + 1][x][y] %= md;
				
				if (s[i] == '0' && y > 0) {
					f[i][x][y - 1] += f[i][x][y];
					f[i][x][y - 1] %= md;
				}
				
				if (s[i] == '1' && x > 0) {
					f[i][x - 1][y] += f[i][x][y];
					f[i][x - 1][y] %= md;
				}
			}
	
	for (int x = n; x >= 0; x--)
		for (int y = n; y >= 0; y--) {
			if (x > 0) {
				f[n][x - 1][y] += f[n][x][y];
				f[n][x - 1][y] %= md;
			}
			
			if (y > 0) {
				f[n][x][y - 1] += f[n][x][y];
				f[n][x][y - 1] %= md;
			}
		}
	
	printf("%d\n", f[n][0][0]);
	
	return 0;
}