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

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int MOD = 998244353, N = 305;
int dp[N][N][N][2], mn_suf[N], zero_on_suf[N];
bool dp2[N][N][N];

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

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

	string s;
	cin >> s;

	int n = s.size();

	for (int i = n - 1; i >= 0; i--) {
		zero_on_suf[i] = zero_on_suf[i + 1];
		if (s[i] == '0')
			zero_on_suf[i]++;
	}

	dp[0][0][0][0] = 1;
    dp[0][0][0][1] = 1;

	for (int i = 0; i < n; i++) {
		char c = s[n - 1 - i];

		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				for (int h = 0; h < 2; h++) {
					if (dp[i][j][k][h]) {

						if (c == '0' && h == 0) {
							add(dp[i + 1][j][k][h], dp[i][j][k][h]);
                            add(dp[i + 1][j][k][1], dp[i][j][k][h]);
						}
						else if (j < n) {
							add(dp[i][j + 1][k][h], dp[i][j][k][h]);
						}

						if (c == '1' && h == 0) {
							add(dp[i + 1][j][k][h], dp[i][j][k][h]);
                            add(dp[i + 1][j][k][1], dp[i][j][k][h]);
						}
						else if (k < n) {
							add(dp[i][j][k + 1][h], dp[i][j][k][h]);
						}
					}
				}
			}
		}
	}

	dp2[0][0][0] = true;

	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (dp2[i][j][k]) {
					int rem = n - i - j - k;
					for (int x = 0; x <= min(rem, 2); x++) {
						for (int p = 0; p <= min(2 - x, j); p++) {
							int q = 2 - x - p;

							if (q > k)
								continue;

							int nj = j - p, nk = k - q, z = 0;

							char oper[2];

							if (x > 0)
								oper[z++] = s[n - rem];
							if (x > 1)
								oper[z++] = s[n - rem + 1];

							if (p > 0)
								oper[z++] = '0';
							if (p > 1)
								oper[z++] = '0';

							if (q > 0)
								oper[z++] = '1';
							if (q > 1)
								oper[z++] = '1';

							for (int h = 0; h < 2; h++) {
								if (oper[h] == '0')
									dp2[i + 1][nj + 1][nk] = true;
								if (oper[h] == '1')
									dp2[i + 1][nj][nk + 1] = true;
							}
							
						}
					}
				}
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			mn_suf[j] = N;
		}

		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (dp2[i][j][k]) {
					int suf = n - i - j - k;
					mn_suf[j + zero_on_suf[n - suf]] = 
						min(mn_suf[j + zero_on_suf[n - suf]], suf);
				}
			}
		}

        for (int j = 0; j <= n; j++) {
            if (mn_suf[j] != N) {
                int x = j - zero_on_suf[n - mn_suf[j]],
                    y = n - i - x - mn_suf[j];
                // cout << mn_suf[j] << " " << x << " " << y << " " << dp[mn_suf[j]][x][y][1] << "\n";
                add(ans, dp[mn_suf[j]][x][y][1]);
            }
        }
	}

	cout << ans << "\n";

	return 0;
}
### Prompt

Your challenge is to write 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
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int MOD = 998244353, N = 305;
int dp[N][N][N][2], mn_suf[N], zero_on_suf[N];
bool dp2[N][N][N];

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

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

	string s;
	cin >> s;

	int n = s.size();

	for (int i = n - 1; i >= 0; i--) {
		zero_on_suf[i] = zero_on_suf[i + 1];
		if (s[i] == '0')
			zero_on_suf[i]++;
	}

	dp[0][0][0][0] = 1;
    dp[0][0][0][1] = 1;

	for (int i = 0; i < n; i++) {
		char c = s[n - 1 - i];

		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				for (int h = 0; h < 2; h++) {
					if (dp[i][j][k][h]) {

						if (c == '0' && h == 0) {
							add(dp[i + 1][j][k][h], dp[i][j][k][h]);
                            add(dp[i + 1][j][k][1], dp[i][j][k][h]);
						}
						else if (j < n) {
							add(dp[i][j + 1][k][h], dp[i][j][k][h]);
						}

						if (c == '1' && h == 0) {
							add(dp[i + 1][j][k][h], dp[i][j][k][h]);
                            add(dp[i + 1][j][k][1], dp[i][j][k][h]);
						}
						else if (k < n) {
							add(dp[i][j][k + 1][h], dp[i][j][k][h]);
						}
					}
				}
			}
		}
	}

	dp2[0][0][0] = true;

	for (int i = 0; i < n - 1; i++) {
		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (dp2[i][j][k]) {
					int rem = n - i - j - k;
					for (int x = 0; x <= min(rem, 2); x++) {
						for (int p = 0; p <= min(2 - x, j); p++) {
							int q = 2 - x - p;

							if (q > k)
								continue;

							int nj = j - p, nk = k - q, z = 0;

							char oper[2];

							if (x > 0)
								oper[z++] = s[n - rem];
							if (x > 1)
								oper[z++] = s[n - rem + 1];

							if (p > 0)
								oper[z++] = '0';
							if (p > 1)
								oper[z++] = '0';

							if (q > 0)
								oper[z++] = '1';
							if (q > 1)
								oper[z++] = '1';

							for (int h = 0; h < 2; h++) {
								if (oper[h] == '0')
									dp2[i + 1][nj + 1][nk] = true;
								if (oper[h] == '1')
									dp2[i + 1][nj][nk + 1] = true;
							}
							
						}
					}
				}
			}
		}
	}

	int ans = 0;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j <= n; j++) {
			mn_suf[j] = N;
		}

		for (int j = 0; j <= n; j++) {
			for (int k = 0; k <= n; k++) {
				if (dp2[i][j][k]) {
					int suf = n - i - j - k;
					mn_suf[j + zero_on_suf[n - suf]] = 
						min(mn_suf[j + zero_on_suf[n - suf]], suf);
				}
			}
		}

        for (int j = 0; j <= n; j++) {
            if (mn_suf[j] != N) {
                int x = j - zero_on_suf[n - mn_suf[j]],
                    y = n - i - x - mn_suf[j];
                // cout << mn_suf[j] << " " << x << " " << y << " " << dp[mn_suf[j]][x][y][1] << "\n";
                add(ans, dp[mn_suf[j]][x][y][1]);
            }
        }
	}

	cout << ans << "\n";

	return 0;
}
```