#include <bits/stdc++.h>
using namespace std;

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }

	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

using num = modnum<998244353>;

template <typename T> void set_min(T& a, T b) {
	if (b < a) a = b;
}

const int INF = 1e8;
const int M = 305;
string s;
int pref[M][M];
bool ok[3][M][M];

num dp[M][M], newdp[M][M];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	int n = int(s.size());
	// pref[i][j]
	{
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				pref[i][j] = INF;
			}
		}
		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 <= n; i++) {
				for (int j = 0; j <= n; j++) {
					if (!ok[c0][i][j]) continue;
					if (i && s[k] == '1') {
						ok[c1][i-1][j+1] = true;
					}
					if (i && s[k] == '0') {
						ok[c1][i][j] = true;
					}
					if (j && s[k] == '0') {
						ok[c1][i+1][j-1] = true;
					}
					if (j && s[k] == '1') {
						ok[c1][i][j] = true;
					}
					if (k+1 < n) {
						for (int z = 0; z < 2; z++) {
							if (s[k]-'0' == z || s[k+1]-'0' == z) {
								ok[c2][i+(z==0)][j+(z==1)] = true;
							}
						}
					}
				}
			}
			c0 = (c0+1) % 3;
			c1 = (c1+1) % 3;
			c2 = (c2+1) % 3;
			for (int i = 0; i <= n; i++) {
				for (int j = 0; j <= n; j++) {
					if (ok[c0][i][j] && pref[i][j] == INF) {
						pref[i][j] = k+1;
					}
				}
			}
		}
	}

	num total = 0;
	reverse(s.begin(), s.end());
	dp[0][0] = 1;
	for (int k = 0; k < n; k++) {
		for (int i = 0; i <= k+1; i++) {
			for (int j = 0; i+j <= k+1; j++) {
				newdp[i][j] = 0;
			}
		}
		for (int i = 0; i <= k; i++) {
			for (int j = 0; i+j <= k; j++) {
				int z = s[k-i-j]-'0';
				newdp[i][j] += dp[i][j];
				if (z == 0) {
					newdp[i][j+1] += dp[i][j];
				} else if (z == 1) {
					newdp[i+1][j] += dp[i][j];
				} else assert(false);
			}
		}
		for (int i = 0; i <= k+1; i++) {
			for (int j = 0; i+j <= k+1; j++) {
				dp[i][j] = newdp[i][j];
			}
		}
		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];
				}
			}
		}
	}
	cout << total << '\n';
}

### Prompt

Create a solution in cpp for 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>
using namespace std;

template <int MOD_> struct modnum {
	static constexpr int MOD = MOD_;
	static_assert(MOD_ > 0, "MOD must be positive");

private:
	using ll = long long;

	int v;

	static int minv(int a, int m) {
		a %= m;
		assert(a);
		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
	}

public:

	modnum() : v(0) {}
	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
	explicit operator int() const { return v; }
	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }

	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }

	modnum inv() const {
		modnum res;
		res.v = minv(v, MOD);
		return res;
	}
	friend modnum inv(const modnum& m) { return m.inv(); }
	modnum neg() const {
		modnum res;
		res.v = v ? MOD-v : 0;
		return res;
	}
	friend modnum neg(const modnum& m) { return m.neg(); }

	modnum operator- () const {
		return neg();
	}
	modnum operator+ () const {
		return modnum(*this);
	}

	modnum& operator ++ () {
		v ++;
		if (v == MOD) v = 0;
		return *this;
	}
	modnum& operator -- () {
		if (v == 0) v = MOD;
		v --;
		return *this;
	}
	modnum& operator += (const modnum& o) {
		v += o.v;
		if (v >= MOD) v -= MOD;
		return *this;
	}
	modnum& operator -= (const modnum& o) {
		v -= o.v;
		if (v < 0) v += MOD;
		return *this;
	}
	modnum& operator *= (const modnum& o) {
		v = int(ll(v) * ll(o.v) % MOD);
		return *this;
	}
	modnum& operator /= (const modnum& o) {
		return *this *= o.inv();
	}

	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
};

using num = modnum<998244353>;

template <typename T> void set_min(T& a, T b) {
	if (b < a) a = b;
}

const int INF = 1e8;
const int M = 305;
string s;
int pref[M][M];
bool ok[3][M][M];

num dp[M][M], newdp[M][M];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> s;
	int n = int(s.size());
	// pref[i][j]
	{
		for (int i = 0; i <= n; i++) {
			for (int j = 0; j <= n; j++) {
				pref[i][j] = INF;
			}
		}
		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 <= n; i++) {
				for (int j = 0; j <= n; j++) {
					if (!ok[c0][i][j]) continue;
					if (i && s[k] == '1') {
						ok[c1][i-1][j+1] = true;
					}
					if (i && s[k] == '0') {
						ok[c1][i][j] = true;
					}
					if (j && s[k] == '0') {
						ok[c1][i+1][j-1] = true;
					}
					if (j && s[k] == '1') {
						ok[c1][i][j] = true;
					}
					if (k+1 < n) {
						for (int z = 0; z < 2; z++) {
							if (s[k]-'0' == z || s[k+1]-'0' == z) {
								ok[c2][i+(z==0)][j+(z==1)] = true;
							}
						}
					}
				}
			}
			c0 = (c0+1) % 3;
			c1 = (c1+1) % 3;
			c2 = (c2+1) % 3;
			for (int i = 0; i <= n; i++) {
				for (int j = 0; j <= n; j++) {
					if (ok[c0][i][j] && pref[i][j] == INF) {
						pref[i][j] = k+1;
					}
				}
			}
		}
	}

	num total = 0;
	reverse(s.begin(), s.end());
	dp[0][0] = 1;
	for (int k = 0; k < n; k++) {
		for (int i = 0; i <= k+1; i++) {
			for (int j = 0; i+j <= k+1; j++) {
				newdp[i][j] = 0;
			}
		}
		for (int i = 0; i <= k; i++) {
			for (int j = 0; i+j <= k; j++) {
				int z = s[k-i-j]-'0';
				newdp[i][j] += dp[i][j];
				if (z == 0) {
					newdp[i][j+1] += dp[i][j];
				} else if (z == 1) {
					newdp[i+1][j] += dp[i][j];
				} else assert(false);
			}
		}
		for (int i = 0; i <= k+1; i++) {
			for (int j = 0; i+j <= k+1; j++) {
				dp[i][j] = newdp[i][j];
			}
		}
		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];
				}
			}
		}
	}
	cout << total << '\n';
}

```