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 MOD = 998244353;
inline void Add(int &x, int y) { (x += y) >= MOD && (x -= MOD); }

int n;
char s[310];
int dp[310][310][310];
// dp[pos][cnt0][cnt1]
bool can[310][310][310];
// can[pos][cnt0][cnt1]

int main() {
	scanf(" %s", s + 1), n = strlen(s + 1);
	dp[n + 1][0][0] = 1;
	for (int i = n + 1; i; --i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) {
				Add(dp[i - 1][j][k], dp[i][j][k]);
				int c = s[i - 1] & 15;
				if (!c) Add(dp[i][j][k + 1], dp[i][j][k]);
				else Add(dp[i][j + 1][k], dp[i][j][k]);
			}
	can[0][0][0] = true;
	for (int i = 0; i <= n; ++i)
		for (int j = n; ~j; --j)
			for (int k = n; ~k; --k) if (can[i][j][k]) {
				if (j) can[i][j - 1][k] = true;
				if (k) can[i][j][k - 1] = true;
				can[i + 1][j][k] = true;
				if (i < n && s[i + 1] == '0' && k) can[i + 1][j + 1][k - 1] = true;
				if (i < n && s[i + 1] == '1' && j) can[i + 1][j - 1][k + 1] = true;
				if (i < n - 1 && (s[i + 1] == '0' || s[i + 2] == '0')) can[i + 2][j + 1][k] = true;
				if (i < n - 1 && (s[i + 1] == '1' || s[i + 2] == '1')) can[i + 2][j][k + 1] = true;
			}
	int ans = 0;
	for (int i = 1; i <= n; ++i)
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) if (can[i][j][k]) Add(ans, dp[i + 1][j][k]);
	printf("%d\n", ans);
	return 0;
}