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>
#define ll long long
#define db long double
#define x first
#define y second
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()

using namespace std;

const int mod = 998244353;

const int N = 307;

int dp[N][N][N];
bool dp2[N][N][N];

inline int sum(int x, int y) {
	if (x+y < 0) return x+y+mod;
	if (x+y >= mod) return x+y-mod;
	return x+y;
}

inline int mult(int x, int y) {
	return ((ll) x * y) % mod;
}

int main(){
#ifdef LOCAL
	freopen("H_input.txt", "r", stdin);
	//freopen("H_output.txt", "w", stdout);
#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	string s;
	cin >> s;

	dp[0][0][0] = 1;
	for (int len = 0; len <= s.size(); ++len) {
		for (int zeros = 0; zeros <= s.size(); ++zeros) {
			for (int ones = 0; ones <= s.size(); ++ones) {

				if (len == 0) {
					if (ones) dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len][ones-1][zeros]);
					if (zeros) dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len][ones][zeros - 1]);
				}
				else {
					if (s[s.size() - len] == '0') {
						if (ones) dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len][ones-1][zeros]);
						dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len - 1][ones][zeros]);
					}
					else {
						if (zeros) dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len][ones][zeros - 1]);
						dp[len][ones][zeros] = sum(dp[len][ones][zeros], dp[len - 1][ones][zeros]);
					}
				}

			}
		}
	}

	//cout << dp[0][1][0] << endl;

	dp2[0][0][0] = true;
	for (int i = 0; i + 1 < s.size(); ++i) {
		for (int zeros = 0; zeros <= s.size(); ++zeros) {
			for (int ones = 0; ones <= s.size(); ++ones) {
				//cout << i << " " << zeros << " " << ones << " " << dp2[i][zeros][ones] << endl;
				if (!dp2[i][zeros][ones]) continue;
				int guys = s.size() - i - zeros - ones;

				if (guys >= 2) {
					if (s[s.size() - guys] == '0' || s[s.size() - guys + 1] == '0') {
						dp2[i+1][zeros+1][ones] = true;
					}
					if (s[s.size() - guys] == '1' || s[s.size() - guys + 1] == '1') {
						dp2[i+1][zeros][ones+1] = true;
					}
				}

				if (guys >= 1) {
					if (s[s.size() - guys] == '0') {
						if (zeros > 0) {
							dp2[i+1][zeros][ones] = true;
						}
						if (ones > 0) {
							dp2[i+1][zeros][ones] = true;
							dp2[i+1][zeros+1][ones-1] = true;
						}
					}
					else {
						if (zeros > 0) {
							dp2[i+1][zeros][ones] = true;
							dp2[i+1][zeros-1][ones+1] = true;
						}
						if (ones > 0) {
							dp2[i+1][zeros][ones] = true;
						}
					}
				}

				if (zeros + ones >= 2) {
					if (zeros > 0) dp2[i+1][zeros-1][ones] = true;
					if (ones > 0) dp2[i+1][zeros][ones-1] = true;
				}

			}
		}
	}

	vector<int> pref_zero(s.size()+1);
	pref_zero[0] = 0;

	for (int i = 0; i < s.size(); ++i) pref_zero[i+1] = pref_zero[i] + (s[i] == '0');

	vector<int> pref_one(s.size()+1);
	pref_one[0] = 0;

	for (int i = 0; i < s.size(); ++i) pref_one[i+1] = pref_one[i] + (s[i] == '1');

	int ans = 0;

	for (int zeros = 0; zeros <= s.size(); ++zeros) {
		for (int ones = 0; ones+zeros <= s.size(); ++ ones) {
			int G = -1;

			int U, W;

			int Q = s.size() - ones - zeros;

			for (int step = 0; step <= s.size(); ++step) {
				int z_need = zeros - (pref_zero.back() - pref_zero[step]);
				int o_need = ones - (pref_one.back() - pref_one[step]);

				if (z_need < 0 || o_need < 0) continue;
				if (dp2[Q][z_need][o_need]) G = step, U=z_need, W=o_need;
			}

			//if (G!=-1) cout << " === " << zeros << " " << ones << " " << G << " " << dp[s.size() - G][U][W] << " " << U << " " << W << endl;

			if (G!=-1) ans = sum(ans, dp[s.size() - G][W][U]);
		}
	}

	cout << ans;





}