#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 305, mod = 998244353;
int n, dp[MX][MX][MX];
ll fac[2 * MX], inv[2 * MX], res = 1;
string s;

ll pot (ll b, int p) {
	ll res = 1;
	while (p) {
		if (p & 1) (res *= b) %= mod;
		(b *= b) %= mod;
		p /= 2;
	}
	return res;
}

ll comb (int n, int k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);

	fac[0] = inv[0] = 1;
	for (int i = 1; i < 2 * MX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = pot(fac[i], mod - 2);
	}

	cin >> s;
	n = s.size();
	
	dp[0][0][0] = 1;

	forn (i, n) forn (j, n) forn (k, n) if (dp[i][j][k]) {
		if (i + 1 < n) {
			if (s[i] == '0' || s[i + 1] == '0') dp[i + 2][j + 1][k] = 1;
			if (s[i] == '1' || s[i + 1] == '1') dp[i + 2][j][k + 1] = 1;
			dp[i + 1][j][k] = 1;
		}

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

	for (int i = n - 1, x = 0, y = 0; i >= 0; i--) {
		if (s[i] == '0') y++;
		else x++;

		forn (j, n) forn (k, n) if (dp[i + 1][j][k]) {
			ll a = !j && !x ? 1 : comb(j + x - 1, j);
			ll b = !k && !y ? 1 : comb(k + y - 1, k);
			(res += a * b) %= mod;
		}
	}

	cout << res << endl;

	return 0;
}

### Prompt

Please create a solution in cpp 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
#include <bits/stdc++.h>
 
#define endl '\n'
#define fi first
#define se second
#define MOD(n,k) ( ( ((n) % (k)) + (k) ) % (k))
#define forn(i,n) for (int i = 0; i < n; i++)
#define forr(i,a,b) for (int i = a; i <= b; i++)
#define all(v) v.begin(), v.end()
#define pb(x) push_back(x)
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;

const int MX = 305, mod = 998244353;
int n, dp[MX][MX][MX];
ll fac[2 * MX], inv[2 * MX], res = 1;
string s;

ll pot (ll b, int p) {
	ll res = 1;
	while (p) {
		if (p & 1) (res *= b) %= mod;
		(b *= b) %= mod;
		p /= 2;
	}
	return res;
}

ll comb (int n, int k) {
	if (n < 0 || k < 0 || n < k) return 0;
	return fac[n] * inv[k] % mod * inv[n - k] % mod;
}

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);

	fac[0] = inv[0] = 1;
	for (int i = 1; i < 2 * MX; i++) {
		fac[i] = fac[i - 1] * i % mod;
		inv[i] = pot(fac[i], mod - 2);
	}

	cin >> s;
	n = s.size();
	
	dp[0][0][0] = 1;

	forn (i, n) forn (j, n) forn (k, n) if (dp[i][j][k]) {
		if (i + 1 < n) {
			if (s[i] == '0' || s[i + 1] == '0') dp[i + 2][j + 1][k] = 1;
			if (s[i] == '1' || s[i + 1] == '1') dp[i + 2][j][k + 1] = 1;
			dp[i + 1][j][k] = 1;
		}

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

	for (int i = n - 1, x = 0, y = 0; i >= 0; i--) {
		if (s[i] == '0') y++;
		else x++;

		forn (j, n) forn (k, n) if (dp[i + 1][j][k]) {
			ll a = !j && !x ? 1 : comb(j + x - 1, j);
			ll b = !k && !y ? 1 : comb(k + y - 1, k);
			(res += a * b) %= mod;
		}
	}

	cout << res << endl;

	return 0;
}

```