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 = 310;
const int mod = 998244353;

int n;
char S[maxn];
bool ok[maxn][maxn][maxn];
int dp[maxn][maxn], ndp[maxn][maxn]; // cnt of 0 not in "lcs"

int mo(int x) {
	return (x >= mod) ? (x - mod) : x;
}

int main() {
	scanf("%s", S+1);
	n = int (strlen(S + 1));
	ok[0][0][0] = true;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= i; j++) {
			for (int k = 0; k <= i-j; k++) {
				if (ok[i][j][k]) {
					{
						// use S[i+1]
						ok[i+1][j][k] = true;
						if (j && S[i+1] == '1') ok[i+1][j-1][k+1] = true;
						if (k && S[i+1] == '0') ok[i+1][j+1][k-1] = true;
					}
					if (i + 2 <= n) {
						// use S[i+1] && S[i+2]
						if (S[i+1] == '0' || S[i+2] == '0') {
							ok[i+2][j+1][k] = true;
						}
						if (S[i+1] == '1' || S[i+2] == '1') {
							ok[i+2][j][k+1] = true;
						}
					}
				}
			}
		}
	}
	for (int i = 0; i <= n; i++) {
		for (int j = i; j >= 0; j--) {
			for (int k = i-j; k >= 0; k--) {
				if (!ok[i][j][k]) continue;
				if (j && k) ok[i][j-1][k-1] = true;
				if (j >= 2) ok[i][j-2][k] = true;
				if (k >= 2) ok[i][j][k-2] = true;
			}
		}
	}
	int ans = 0;
	dp[0][0] = 1;
	for (int len = 1; len <= n; len++) {
		for (int i = 0; i <= len; i++) {
			for (int j = 0; j <= len-i; j++) {
				ndp[i][j] = 0;
				// from i
				if (i != n) {
					if (S[n - i] == '0') {
						ndp[i][j] = mo(ndp[i][j] + dp[i][j]);
					} else if (j) {
						ndp[i][j] = mo(ndp[i][j] + dp[i][j-1]);
					}
				}
				// from i-1
				if (i) ndp[i][j] = mo(ndp[i][j] + dp[i-1][j]);
			}
		}
		for (int i = 0; i <= len; i++) {
			for (int j = 0; j <= len-i; j++) {
				dp[i][j] = ndp[i][j];
				if (ok[n-i][j][len-i-j]) {
					ans = mo(ans + dp[i][j]);
				}
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}