#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXLEN = 300;
const int MOD = 998244353;
void inc(int& a, int b) { if ((a += b) >= MOD) a -= MOD; }
void dec(int& a, int b) { inc(a, MOD - b); }

char s[MAXLEN + 1]; int slen;

int dp[MAXLEN + 1][MAXLEN + 1][MAXLEN + 1];
bool can[MAXLEN + 1][MAXLEN + 1][MAXLEN + 1];

int solve() {
	for (int i = slen; i >= 0; --i) REPE(a, slen) REPE(b, slen) {
		dp[i][a][b] = i == slen && a == 0 && b == 0 ? 1 : 0;
		if (a > 0 && (i >= slen || s[i] != '0')) inc(dp[i][a][b], dp[i][a - 1][b]);
		if (b > 0 && (i >= slen || s[i] != '1')) inc(dp[i][a][b], dp[i][a][b - 1]);
		if (i < slen) inc(dp[i][a][b], dp[i + 1][a][b]);
	}

	REPE(i, slen) REPE(a, slen) REPE(b, slen) can[i][a][b] = false;
	can[0][0][0] = true;
	int ret = 0;
	REPE(i, slen) for (int a = slen; a >= 0; --a) for (int b = slen; b >= 0; --b) if (can[i][a][b]) {
		//printf("%d %d %d = %d\n", i, a, b, dp[i][a][b]);
		inc(ret, dp[i][a][b]);
		if (i - 1 >= 0 && s[i - 1] == '0' && a >= 1 && can[i - 1][a - 1][b]) dec(ret, dp[i - 1][a - 1][b]);
		if (i - 1 >= 0 && s[i - 1] == '1' && b >= 1 && can[i - 1][a][b - 1]) dec(ret, dp[i - 1][a][b - 1]);
		if (a >= 2) can[i][a - 1][b] = true;
		if (a >= 1 && b >= 1) can[i][a - 1][b] = can[i][a][b - 1] = true;
		if (b >= 2) can[i][a][b - 1] = true;
		if (i < slen) {
			if (a >= 1 || b >= 1) can[i + 1][a][b] = true;
			if (s[i] == '0' && b >= 1) can[i + 1][a + 1][b - 1] = true;
			if (s[i] == '1' && a >= 1) can[i + 1][a - 1][b + 1] = true;
		}
		if (i + 1 < slen) {
			if (s[i] == '0' || s[i + 1] == '0') can[i + 2][a + 1][b] = true;
			if (s[i] == '1' || s[i + 1] == '1') can[i + 2][a][b + 1] = true;
		}
	}
	return ret;
}

void run() {
	scanf("%s", s); slen = strlen(s);
	printf("%d\n", solve());
}

int main() {
	run();
	return 0;
}

### 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 <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
#include <chrono>
#include <random>
using namespace std;

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
std::mt19937 rnd((int)std::chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }

const int MAXLEN = 300;
const int MOD = 998244353;
void inc(int& a, int b) { if ((a += b) >= MOD) a -= MOD; }
void dec(int& a, int b) { inc(a, MOD - b); }

char s[MAXLEN + 1]; int slen;

int dp[MAXLEN + 1][MAXLEN + 1][MAXLEN + 1];
bool can[MAXLEN + 1][MAXLEN + 1][MAXLEN + 1];

int solve() {
	for (int i = slen; i >= 0; --i) REPE(a, slen) REPE(b, slen) {
		dp[i][a][b] = i == slen && a == 0 && b == 0 ? 1 : 0;
		if (a > 0 && (i >= slen || s[i] != '0')) inc(dp[i][a][b], dp[i][a - 1][b]);
		if (b > 0 && (i >= slen || s[i] != '1')) inc(dp[i][a][b], dp[i][a][b - 1]);
		if (i < slen) inc(dp[i][a][b], dp[i + 1][a][b]);
	}

	REPE(i, slen) REPE(a, slen) REPE(b, slen) can[i][a][b] = false;
	can[0][0][0] = true;
	int ret = 0;
	REPE(i, slen) for (int a = slen; a >= 0; --a) for (int b = slen; b >= 0; --b) if (can[i][a][b]) {
		//printf("%d %d %d = %d\n", i, a, b, dp[i][a][b]);
		inc(ret, dp[i][a][b]);
		if (i - 1 >= 0 && s[i - 1] == '0' && a >= 1 && can[i - 1][a - 1][b]) dec(ret, dp[i - 1][a - 1][b]);
		if (i - 1 >= 0 && s[i - 1] == '1' && b >= 1 && can[i - 1][a][b - 1]) dec(ret, dp[i - 1][a][b - 1]);
		if (a >= 2) can[i][a - 1][b] = true;
		if (a >= 1 && b >= 1) can[i][a - 1][b] = can[i][a][b - 1] = true;
		if (b >= 2) can[i][a][b - 1] = true;
		if (i < slen) {
			if (a >= 1 || b >= 1) can[i + 1][a][b] = true;
			if (s[i] == '0' && b >= 1) can[i + 1][a + 1][b - 1] = true;
			if (s[i] == '1' && a >= 1) can[i + 1][a - 1][b + 1] = true;
		}
		if (i + 1 < slen) {
			if (s[i] == '0' || s[i + 1] == '0') can[i + 2][a + 1][b] = true;
			if (s[i] == '1' || s[i + 1] == '1') can[i + 2][a][b + 1] = true;
		}
	}
	return ret;
}

void run() {
	scanf("%s", s); slen = strlen(s);
	printf("%d\n", solve());
}

int main() {
	run();
	return 0;
}

```