#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int N = 310;
const ll MOD = 998244353;

int dp[N][N][N];
ll dp2[N][N][N];

string s;

void add(ll& a, ll b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> s;
	reverse(ALL(s));
	dp[s.size()][0][0] = 1;
	int n = s.size();

	for (int l = s.size(); l >= 0; --l) {
		for (int i = n - l; i >= 0; --i) {
			for (int j = n - l; j >= 0; --j) {
				if (!dp[l][i][j]) {
					continue;
				}

				if (i) {
					dp[l][i - 1][j] = 1;
				}
				if (j) {
					dp[l][i][j - 1] = 1;
				}
				if (l) {
					dp[l - 1][i][j] = 1;
					if (i && s[l - 1] == '1') {
						dp[l - 1][i - 1][j + 1] = 1;
					}
					if (j && s[l - 1] == '0') {
						dp[l - 1][i + 1][j - 1] = 1;
					}
				}

				if (l >= 2) {
					if (s[l - 1] == '0' || s[l - 2] == '0') {
						dp[l - 2][i + 1][j] = 1;
					}
					if (s[l - 1] == '1' || s[l - 2] == '1') {
						dp[l - 2][i][j + 1] = 1;
					}
				}
			}
		}
	}

	for (int l = 0; l < n; ++l) {
		for (int i = 0; i <= n - l; ++i) {
			for (int j = 0; j <= n - l; ++j) {
				if (dp[l][i][j]) {
					if (i && s[l] == '0') {
						dp[l + 1][i - 1][j] = 1;
					}
					if (j && s[l] == '1') {
						dp[l + 1][i][j - 1] = 1;
					}
				}
			}
		}
	}


	ll ans = 0;
	dp2[0][0][0] = 1;
	for (int l = 0; l <= n; ++l) {
		for (int i = 0; i + l <= n; ++i) {
			for (int j = 0; i + j + l <= n; ++j) {
				if (dp[l][i][j] && l + i + j != 0) {
					//cout << l << " " << i << " " << j << ": " << dp2[l][i][j] << "\n";
					add(ans, dp2[l][i][j]);
				}
				if (l < n && s[l] == '0') {
					add(dp2[l + 1][i][j], dp2[l][i][j]);
				} else {
					add(dp2[l][i + 1][j], dp2[l][i][j]);
				}
				if (l < n && s[l] == '1') {
					add(dp2[l + 1][i][j], dp2[l][i][j]);
				} else {
					add(dp2[l][i][j + 1], dp2[l][i][j]);
				}
			}
		}
	}
	cout << ans << "\n";

	return 0;
}



### Prompt

Your task is to create a cpp solution to the following 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

### Response

```cpp
#ifndef BZ
#pragma GCC optimize "-O3"
#endif
#include <bits/stdc++.h>

#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i < (r); ++i)

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;


/*
ll pw(ll a, ll b) {
	ll ans = 1; while (b) {
		while (!(b & 1)) b >>= 1, a = (a * a) % MOD;
		ans = (ans * a) % MOD, --b;
	} return ans;
}
*/
const int N = 310;
const ll MOD = 998244353;

int dp[N][N][N];
ll dp2[N][N][N];

string s;

void add(ll& a, ll b) {
	a += b;
	if (a >= MOD) {
		a -= MOD;
	}
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cout.setf(ios::fixed), cout.precision(20);
	cin >> s;
	reverse(ALL(s));
	dp[s.size()][0][0] = 1;
	int n = s.size();

	for (int l = s.size(); l >= 0; --l) {
		for (int i = n - l; i >= 0; --i) {
			for (int j = n - l; j >= 0; --j) {
				if (!dp[l][i][j]) {
					continue;
				}

				if (i) {
					dp[l][i - 1][j] = 1;
				}
				if (j) {
					dp[l][i][j - 1] = 1;
				}
				if (l) {
					dp[l - 1][i][j] = 1;
					if (i && s[l - 1] == '1') {
						dp[l - 1][i - 1][j + 1] = 1;
					}
					if (j && s[l - 1] == '0') {
						dp[l - 1][i + 1][j - 1] = 1;
					}
				}

				if (l >= 2) {
					if (s[l - 1] == '0' || s[l - 2] == '0') {
						dp[l - 2][i + 1][j] = 1;
					}
					if (s[l - 1] == '1' || s[l - 2] == '1') {
						dp[l - 2][i][j + 1] = 1;
					}
				}
			}
		}
	}

	for (int l = 0; l < n; ++l) {
		for (int i = 0; i <= n - l; ++i) {
			for (int j = 0; j <= n - l; ++j) {
				if (dp[l][i][j]) {
					if (i && s[l] == '0') {
						dp[l + 1][i - 1][j] = 1;
					}
					if (j && s[l] == '1') {
						dp[l + 1][i][j - 1] = 1;
					}
				}
			}
		}
	}


	ll ans = 0;
	dp2[0][0][0] = 1;
	for (int l = 0; l <= n; ++l) {
		for (int i = 0; i + l <= n; ++i) {
			for (int j = 0; i + j + l <= n; ++j) {
				if (dp[l][i][j] && l + i + j != 0) {
					//cout << l << " " << i << " " << j << ": " << dp2[l][i][j] << "\n";
					add(ans, dp2[l][i][j]);
				}
				if (l < n && s[l] == '0') {
					add(dp2[l + 1][i][j], dp2[l][i][j]);
				} else {
					add(dp2[l][i + 1][j], dp2[l][i][j]);
				}
				if (l < n && s[l] == '1') {
					add(dp2[l + 1][i][j], dp2[l][i][j]);
				} else {
					add(dp2[l][i][j + 1], dp2[l][i][j]);
				}
			}
		}
	}
	cout << ans << "\n";

	return 0;
}



```