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 N = 305;
const long long mod = 998244353ll;

int n;
bool f[N][N][N];
long long g[N][N][N], ans = 0ll;
char str[N];

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

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= i - j; k++) f[i][j][k] = false;
		}
	}
	f[0][0][0] = true;
	for (int i = 0; i < n; i++) {
		for (int j = i; j >= 0; j--) {
			for (int k = i - j; k >= 0; k--) {
				if (!f[i][j][k]) continue;
				if (i < n - 1) {
					if (str[i] == '0' || str[i + 1] == '0') f[i + 2][j + 1][k] = true;
					if (str[i] == '1' || str[i + 1] == '1') f[i + 2][j][k + 1] = true;
				}
				if (j && j + k >= 2) f[i][j - 1][k] = true;
				if (k && j + k >= 2) f[i][j][k - 1] = true;
				if (j + k) f[i + 1][j][k] = true;
				if (j && str[i] == '1') f[i + 1][j - 1][k + 1] = true;
				if (k && str[i] == '0') f[i + 1][j + 1][k - 1] = true;
			}
		}
	}
	for (int i = 0; i <= n + 1; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n - j; k++) g[i][j][k] = 0ll;
		}
	}
	g[n + 1][0][0] = 1ll;
	for (int i = n + 1; i > 1; i--) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n - j; k++) {
				if (str[i - 2] == '0') {
					g[i - 1][j + 1][k] = (g[i - 1][j + 1][k] + g[i][j][k]) % mod;
					g[i][j][k + 1] = (g[i][j][k + 1] + g[i][j][k]) % mod;
				}
				else {
					g[i - 1][j][k + 1] = (g[i - 1][j][k + 1] + g[i][j][k]) % mod;
					g[i][j + 1][k] = (g[i][j + 1][k] + g[i][j][k]) % mod;
				}
			}
		}
	}

	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n - i; j++) {
			bool flag = false;
			long long tmp = 0ll;
			int zero = 0, one = 0;
			for (int k = n + 1; k; k--) {
				if (k <= n) {
					if (str[k - 1] == '0') zero++;
					else one++;
				}
				if (i - zero >= 0 && j - one >= 0 && f[k - 1][i - zero][j - one]) flag = true;
				if (flag) {
					tmp = (tmp + g[k][i][j]) % mod;
					ans = (ans + g[k][i][j]) % mod;
				}
			}
		}
	}
	printf("%lld\n", ans);
	return 0;
}