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;

typedef unsigned int uint;
typedef unsigned long long ull;
const uint MOD = 998244353;
const ull LMOD = (ull(7e18) / MOD) * MOD;

const int M = 310;
string s;
int n;
int pref[M][M];
bool ok[3][M][M];

uint dp[M][M];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	n = int(s.size());
	{
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				pref[i][j] = M;
			}
		}
		pref[0][0] = 0;
		int c0 = 0, c1 = 1, c2 = 2;
		ok[c0][0][0] = true;
		for (int k = 0; k < n; k++) {
			for (int i = 0; i <= k; i++) {
				for (int j = 0; i+j <= k; j++) {
					if (!ok[c0][i][j]) continue;
					// 直接扔掉
					ok[c1][i][j] = true;
					if (i && s[k] == '1') {
						ok[c1][i-1][j+1] = true;
					}
					if (j && s[k] == '0') {
						ok[c1][i+1][j-1] = true;
					}
					if (k+1 < n) {
						for (int zz = 0; zz < 2; zz++) {
							if (zz == s[k]-'0' || zz == s[k+1]-'0') {
								ok[c2][i + (zz==0)][j + (zz==1)] = true;
							}
						}
					}
				}
			}
			c0 = (c0+1) % 3;
			c1 = (c1+1) % 3;
			c2 = (c2+1) % 3;
			for (int i = 0; i <= k+1; i++) {
				for (int j = 0; i+j <= k+1; j++) {
					if (ok[c0][i][j] && pref[i][j] == M) {
						pref[i][j] = k+1;
					}
				}
			}
		}
	}

	ull total = 0;
	reverse(s.begin(), s.end());
	dp[0][0] = 1;
	for (int k = 0; k < n; k++) {
		for (int i = k; i >= 0; i--) {
			for (int j = k-i; j >= 0; j--) {
				if (!dp[i][j]) continue;
				int z = s[k-i-j] - '0';
				if (z == 0) {
					dp[i][j+1] += dp[i][j];
					if (dp[i][j+1] >= MOD) dp[i][j+1] -= MOD;
				} else {
					dp[i+1][j] += dp[i][j];
					if (dp[i+1][j] >= MOD) dp[i+1][j] -= MOD;
				}
			}
		}
		for (int i = 0; i <= k+1; i++) {
			for (int j = 0; i+j <= k+1; j++) {
				int rest = (k+1) - (i+j);
				if (pref[i][j] <= n-rest) {
					total += dp[i][j];
				}
			}
		}
	}
	total %= MOD;
	cout << uint(total) << '\n';
}