// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define tisic 47
#define soclose 1e-8
#define patkan 9
#define ff first
#define ss second
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

template <typename T>
T abs(T x) {return (x < 0) ? -x : x;}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? x * a % mod : x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string S;
	cin >> S;
	int N = S.length();
	vector< vector< vector<char> > > dp(N+1, vector< vector<char> >(N+1, vector<char>(N+1, 0)));
	dp[0][0][0] = 1;
	for(int i = 0; i < N; i++) for(int j = N; j >= 0; j--) for(int k = N-j; k >= 0; k--) if(dp[i][j][k]) {
		int jn = j + (S[i] == '0'), kn = k + (S[i] == '1');
		if(j) dp[i+1][jn-1][kn] = 1;
		if(k) dp[i+1][jn][kn-1] = 1;
		if(j+k) dp[i+1][j][k] = 1;
		if(j+k > 1 && j) dp[i][j-1][k] = 1;
		if(j+k > 1 && k) dp[i][j][k-1] = 1;
		if(i < N-1) {
			dp[i+2][jn][kn] = 1;
			dp[i+2][j + (S[i+1] == '0')][k + (S[i+1] == '1')] = 1;
		}
	}
	cat ans = 0, mod = 998244353;
	vector< vector<int> > min_pref(N+1, vector<int>(N+1, -1));
	for(int i = N, n0 = 0, n1 = 0; i >= 0; i--) {
		if(i < N) n0 += (S[i] == '0'), n1 += (S[i] == '1');
		for(int j = 0; j <= N; j++) for(int k = 0; k <= N; k++)
			if(dp[i][j][k] && min_pref[n0+j][n1+k] == -1) min_pref[n0+j][n1+k] = i;
	}
	vector< vector< vector<cat> > > cnt[2];
	cnt[0].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	cnt[1].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	cnt[0][0][0][0] = 1;
	for(int i = 0; i < N; i++) for(int j = 0; j < N-i; j++) for(int k = 0; k < N-i-j; k++) {
		if(i < N) {
			cnt[0][i+1][j][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[0][i+1][j][k] %= mod;
		}
		if(i == N || S[N-1-i] == '1') {
			cnt[1][i][j+1][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[1][i][j+1][k] %= mod;
		}
		if(i == N || S[N-1-i] == '0') {
			cnt[1][i][j][k+1] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[1][i][j][k+1] %= mod;
		}
	}
	cnt[1].clear();
	cnt[1].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	for(int i = 0; i < N; i++) for(int j = 0; j < N-i; j++) for(int k = 0; k < N-i-j; k++) {
		cnt[1][i][j+1][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
		cnt[1][i][j+1][k] %= mod;
		cnt[1][i][j][k+1] += cnt[0][i][j][k] + cnt[1][i][j][k];
		cnt[1][i][j][k+1] %= mod;
	}
	for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) if(min_pref[i][j] >= 0) {
		int n0 = i, n1 = j;
		for(int k = min_pref[i][j]; k < N; k++) n0 -= (S[k] == '0'), n1 -= (S[k] == '1');
		// cout << i << " " << j << " " << n0 << " " << n1 << " " << N-min_pref[i][j] << " " << cnt[1][N-min_pref[i][j]][n0][n1] << "\n";
		ans += cnt[0][N-min_pref[i][j]][n0][n1] + cnt[1][N-min_pref[i][j]][n0][n1];
	}
	ans %= mod;
	cout << ans << "\n";
}

### Prompt

Please formulate 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
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <chrono>
#include <random>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cstring>
#include <iomanip>
#define dibs reserve
#define OVER9000 1234567890
#define tisic 47
#define soclose 1e-8
#define patkan 9
#define ff first
#define ss second
using uint = unsigned int;
using cat = long long;
using dbl = long double;
constexpr dbl pi = 3.14159265358979323846;
using namespace std;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

template <typename T>
T abs(T x) {return (x < 0) ? -x : x;}

cat pw(cat a, cat e, cat mod) {
	if(e <= 0) return 1;
	cat x = pw(a, e/2, mod);
	x = x * x % mod;
	return (e&1) ? x * a % mod : x;
}

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string S;
	cin >> S;
	int N = S.length();
	vector< vector< vector<char> > > dp(N+1, vector< vector<char> >(N+1, vector<char>(N+1, 0)));
	dp[0][0][0] = 1;
	for(int i = 0; i < N; i++) for(int j = N; j >= 0; j--) for(int k = N-j; k >= 0; k--) if(dp[i][j][k]) {
		int jn = j + (S[i] == '0'), kn = k + (S[i] == '1');
		if(j) dp[i+1][jn-1][kn] = 1;
		if(k) dp[i+1][jn][kn-1] = 1;
		if(j+k) dp[i+1][j][k] = 1;
		if(j+k > 1 && j) dp[i][j-1][k] = 1;
		if(j+k > 1 && k) dp[i][j][k-1] = 1;
		if(i < N-1) {
			dp[i+2][jn][kn] = 1;
			dp[i+2][j + (S[i+1] == '0')][k + (S[i+1] == '1')] = 1;
		}
	}
	cat ans = 0, mod = 998244353;
	vector< vector<int> > min_pref(N+1, vector<int>(N+1, -1));
	for(int i = N, n0 = 0, n1 = 0; i >= 0; i--) {
		if(i < N) n0 += (S[i] == '0'), n1 += (S[i] == '1');
		for(int j = 0; j <= N; j++) for(int k = 0; k <= N; k++)
			if(dp[i][j][k] && min_pref[n0+j][n1+k] == -1) min_pref[n0+j][n1+k] = i;
	}
	vector< vector< vector<cat> > > cnt[2];
	cnt[0].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	cnt[1].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	cnt[0][0][0][0] = 1;
	for(int i = 0; i < N; i++) for(int j = 0; j < N-i; j++) for(int k = 0; k < N-i-j; k++) {
		if(i < N) {
			cnt[0][i+1][j][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[0][i+1][j][k] %= mod;
		}
		if(i == N || S[N-1-i] == '1') {
			cnt[1][i][j+1][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[1][i][j+1][k] %= mod;
		}
		if(i == N || S[N-1-i] == '0') {
			cnt[1][i][j][k+1] += cnt[0][i][j][k] + cnt[1][i][j][k];
			cnt[1][i][j][k+1] %= mod;
		}
	}
	cnt[1].clear();
	cnt[1].resize(N+1, vector< vector<cat> >(N+1, vector<cat>(N+1, 0)));
	for(int i = 0; i < N; i++) for(int j = 0; j < N-i; j++) for(int k = 0; k < N-i-j; k++) {
		cnt[1][i][j+1][k] += cnt[0][i][j][k] + cnt[1][i][j][k];
		cnt[1][i][j+1][k] %= mod;
		cnt[1][i][j][k+1] += cnt[0][i][j][k] + cnt[1][i][j][k];
		cnt[1][i][j][k+1] %= mod;
	}
	for(int i = 0; i <= N; i++) for(int j = 0; j <= N; j++) if(min_pref[i][j] >= 0) {
		int n0 = i, n1 = j;
		for(int k = min_pref[i][j]; k < N; k++) n0 -= (S[k] == '0'), n1 -= (S[k] == '1');
		// cout << i << " " << j << " " << n0 << " " << n1 << " " << N-min_pref[i][j] << " " << cnt[1][N-min_pref[i][j]][n0][n1] << "\n";
		ans += cnt[0][N-min_pref[i][j]][n0][n1] + cnt[1][N-min_pref[i][j]][n0][n1];
	}
	ans %= mod;
	cout << ans << "\n";
}

```