#include <bits/stdc++.h>
using namespace std;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
char str[305];
bool used[305][305][305];
int n;
void go(int i, int j, int k) {
	if (j < 0 || k < 0) return;
	if (used[i][j][k]) return;
	used[i][j][k] = true;
	if (i + 2 <= n) {
		if (str[i] == '0' || str[i + 1] == '0')
			go(i + 2, j + 1, k);
		if (str[i] == '1' || str[i + 1] == '1')
			go(i + 2, j, k + 1);
	}
	if (i + 1 <= n) {
		if (str[i] == '0') {
			go(i + 1, j + 1, k - 1);
			go(i + 1, j, k);
		}
		if (str[i] == '1') {
			go(i + 1, j - 1, k + 1);
			go(i + 1, j, k);
		}
	}
	go(i, j - 1, k);
	go(i, j, k - 1);
}
const int MOD = 998244353;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
Mint dp[305][305][305];
int main() {
	scanf("%s", str);
	n = strlen(str);
	const int INF = 1e9;
	vector<vector<int>> minsuf(n + 1, vector<int>(n + 1, INF));
	go(0, 0, 0);
	for (int i = 0; i <= n; ++i) {
		int c0 = 0, c1 = 0;
		for (int j = i; j < n; ++j) {
			c0 += str[j] == '0';
			c1 += str[j] == '1';
		}
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) {
				if (!used[i][j][k]) continue;
				int d0 = c0 + j;
				int d1 = c1 + k;
				minsuf[d0][d1] = min(minsuf[d0][d1], c0 + c1);
			}
	}
	reverse(str, str + n);
	// Insert j, k into suffix of length i.
	dp[0][0][0] = 1;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) {
				if (!i && !j && !k) continue;
				Mint& ret = dp[i][j][k];
				if (i) {
					if (str[i - 1] == '0') {
						if (j) ret += dp[i - 1][j - 1][k];
						if (k) ret += dp[i][j][k - 1];
					} else {
						if (k) ret += dp[i - 1][j][k - 1];
						if (j) ret += dp[i][j - 1][k];
					}
				} else {
					if (j) ret += dp[i][j - 1][k];
					if (k) ret += dp[i][j][k - 1];
				}
			}
	}
	Mint ans = 0;
	for (int j = 0; j <= n; ++j)
		for (int k = 0; k <= n; ++k) {
			if (!j && !k) continue;
			int s = minsuf[j][k];
			if (s == INF) continue;
			assert(s <= n);
			ans += dp[s][j][k];
		}
	printf("%d\n", ans.val);
}

### 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;
//#define cerr if (false) cerr
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
#define dbv(v) cerr << #v << "="; for (auto _x : v) cerr << _x << ", "; cerr << endl
#define dba(a, n) cerr << #a << "="; for (int _i = 0; _i < (n); ++_i) cerr << a[_i] << ", "; cerr << endl
template <typename A, typename B>
ostream& operator<<(ostream& os, const pair<A, B>& x) {
	return os << "(" << x.first << "," << x.second << ")";
}
typedef long long ll;
typedef long double ld;
char str[305];
bool used[305][305][305];
int n;
void go(int i, int j, int k) {
	if (j < 0 || k < 0) return;
	if (used[i][j][k]) return;
	used[i][j][k] = true;
	if (i + 2 <= n) {
		if (str[i] == '0' || str[i + 1] == '0')
			go(i + 2, j + 1, k);
		if (str[i] == '1' || str[i + 1] == '1')
			go(i + 2, j, k + 1);
	}
	if (i + 1 <= n) {
		if (str[i] == '0') {
			go(i + 1, j + 1, k - 1);
			go(i + 1, j, k);
		}
		if (str[i] == '1') {
			go(i + 1, j - 1, k + 1);
			go(i + 1, j, k);
		}
	}
	go(i, j - 1, k);
	go(i, j, k - 1);
}
const int MOD = 998244353;
struct Mint {
	int val;
	Mint() { val = 0; }
	Mint(const ll& x) {
		val = (-MOD <= x && x < MOD) ? x : x % MOD;
		if (val < 0) val += MOD;
	}
	template <typename U>
	explicit operator U() const { return (U)val; }
	friend bool operator==(const Mint& a, const Mint& b) { return a.val == b.val; }
	friend bool operator!=(const Mint& a, const Mint& b) { return !(a == b); }
	friend bool operator<(const Mint& a, const Mint& b) { return a.val < b.val; }
	Mint& operator+=(const Mint& m) { if ((val += m.val) >= MOD) val -= MOD; return *this; }
	Mint& operator-=(const Mint& m) { if ((val -= m.val) < 0) val += MOD; return *this; }
	Mint& operator*=(const Mint& m) { val = (ll)val * m.val % MOD; return *this; }
	friend Mint modex(Mint a, ll p) {
		assert(p >= 0);
		Mint ans = 1;
		for (; p; p >>= 1, a *= a) if (p & 1) ans *= a;
		return ans;
	}
	Mint& operator/=(const Mint& m) { return *this *= modex(m, MOD - 2); }
	Mint& operator++() { return *this += 1; }
	Mint& operator--() { return *this -= 1; }
	Mint operator++(int) { Mint result(*this); *this += 1; return result; }
	Mint operator--(int) { Mint result(*this); *this -= 1; return result; }
	Mint operator-() const { return Mint(-val); }
	friend Mint operator+(Mint a, const Mint& b) { return a += b; }
	friend Mint operator-(Mint a, const Mint& b) { return a -= b; }
	friend Mint operator*(Mint a, const Mint& b) { return a *= b; }
	friend Mint operator/(Mint a, const Mint& b) { return a /= b; }
	friend ostream& operator<<(ostream& os, const Mint& x) { return os << x.val; }
};
Mint dp[305][305][305];
int main() {
	scanf("%s", str);
	n = strlen(str);
	const int INF = 1e9;
	vector<vector<int>> minsuf(n + 1, vector<int>(n + 1, INF));
	go(0, 0, 0);
	for (int i = 0; i <= n; ++i) {
		int c0 = 0, c1 = 0;
		for (int j = i; j < n; ++j) {
			c0 += str[j] == '0';
			c1 += str[j] == '1';
		}
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) {
				if (!used[i][j][k]) continue;
				int d0 = c0 + j;
				int d1 = c1 + k;
				minsuf[d0][d1] = min(minsuf[d0][d1], c0 + c1);
			}
	}
	reverse(str, str + n);
	// Insert j, k into suffix of length i.
	dp[0][0][0] = 1;
	for (int i = 0; i <= n; ++i) {
		for (int j = 0; j <= n; ++j)
			for (int k = 0; k <= n; ++k) {
				if (!i && !j && !k) continue;
				Mint& ret = dp[i][j][k];
				if (i) {
					if (str[i - 1] == '0') {
						if (j) ret += dp[i - 1][j - 1][k];
						if (k) ret += dp[i][j][k - 1];
					} else {
						if (k) ret += dp[i - 1][j][k - 1];
						if (j) ret += dp[i][j - 1][k];
					}
				} else {
					if (j) ret += dp[i][j - 1][k];
					if (k) ret += dp[i][j][k - 1];
				}
			}
	}
	Mint ans = 0;
	for (int j = 0; j <= n; ++j)
		for (int k = 0; k <= n; ++k) {
			if (!j && !k) continue;
			int s = minsuf[j][k];
			if (s == INF) continue;
			assert(s <= n);
			ans += dp[s][j][k];
		}
	printf("%d\n", ans.val);
}

```