 /*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int Mod = 998244353;
const int MAXN = 305;


int sum(int a, int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}

int mul(int a, int b) {
	return (ll)a * b % Mod;
}



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


int n;
int f[MAXN][MAXN][MAXN];
bool g[MAXN][MAXN][MAXN];
int ans;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//read(FILENAME);
	string s;
	cin >> s;
	n = sz(s);
	g[0][0][0]=1;
	for (int i=1;i<=n;i++) for (int p0=0;p0<=i;p0++) for (int p1=0;p1<=i;p1++) {
		g[i][p0][p1]=g[i-1][p0][p1];
		if (i>=2) {
			if ((s[i-1]=='0'||s[i-2]=='0')&&p0>0) g[i][p0][p1]|=g[i-2][p0-1][p1];
			if ((s[i-1]=='1'||s[i-2]=='1')&&p1>0) g[i][p0][p1]|=g[i-2][p0][p1-1];
		}
		if (s[i-1]=='0'&&p0>0) g[i][p0][p1]|=g[i-1][p0-1][p1+1];
		if (s[i-1]=='1'&&p1>0) g[i][p0][p1]|=g[i-1][p0+1][p1-1];
	}
	f[0][0][0]=1;
	for (int d=0;d<=n;d++) {
		for (int p0=0;p0<=d;p0++) for (int p1=0;p0+p1<=d;p1++) {
			int mt=d-p0-p1;
			if (g[n-mt][p0][p1]) {
				add(ans,f[d][p0][p1]);
			}
			if (d==n) continue;
			char t=s[n-1-mt];
			if (t=='0') add(f[d+1][p0][p1],f[d][p0][p1]);
			else add(f[d+1][p0+1][p1],f[d][p0][p1]);
			if (t=='1') add(f[d+1][p0][p1],f[d][p0][p1]);
			else add(f[d+1][p0][p1+1],f[d][p0][p1]);
		}
	}
	ans = sum(ans, Mod - 1);
	cout << ans << '\n';
	return 0;	 	
}

### 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
 /*
ЗАПУСКАЕМ 
░ГУСЯ░▄▀▀▀▄░РАБОТЯГУ░░
▄███▀░◐░░░▌░░░░░░░
░░░░▌░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▐░░░░░▐░░░░░░░
░░░░▌░░░░░▐▄▄░░░░░
░░░░▌░░░░▄▀▒▒▀▀▀▀▄
░░░▐░░░░▐▒▒▒▒▒▒▒▒▀▀▄
░░░▐░░░░▐▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░▀▄░░░░▀▄▒▒▒▒▒▒▒▒▒▒▀▄
░░░░░░▀▄▄▄▄▄█▄▄▄▄▄▄▄▄▄▄▄▀▄
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░░░▌▌░▌▌░░░░░
░░░░░░░░░▄▄▌▌▄▌▌░░░░░ 
 */
#include <iostream>
#include <complex>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <numeric>
#include <cstring>
#include <ctime>
#include <cstdlib>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <cmath>
#include <bitset>
#include <cassert>
#include <queue>
#include <stack>
#include <deque>
#include <random>


using namespace std;
template<typename T1, typename T2> inline void chkmin(T1 &a, T2 b) {if (a > b) a = b;}
template<typename T1, typename T2> inline void chkmax(T1 &a, T2 b) {if (a < b) a = b;}
#define files(FILENAME) read(FILENAME); write(FILENAME)
#define read(FILENAME) freopen((FILENAME + ".in").c_str(), "r", stdin)
#define write(FILENAME) freopen((FILENAME + ".out").c_str(), "w", stdout)
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define left left228
#define right right228
#define y1 y1228
#define mp make_pair
#define pb push_back
#define y2 y2228
#define rank rank228
using ll = long long;
using ld = long double;
const string FILENAME = "input";
const int Mod = 998244353;
const int MAXN = 305;


int sum(int a, int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}

int mul(int a, int b) {
	return (ll)a * b % Mod;
}



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


int n;
int f[MAXN][MAXN][MAXN];
bool g[MAXN][MAXN][MAXN];
int ans;



int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
 	//read(FILENAME);
	string s;
	cin >> s;
	n = sz(s);
	g[0][0][0]=1;
	for (int i=1;i<=n;i++) for (int p0=0;p0<=i;p0++) for (int p1=0;p1<=i;p1++) {
		g[i][p0][p1]=g[i-1][p0][p1];
		if (i>=2) {
			if ((s[i-1]=='0'||s[i-2]=='0')&&p0>0) g[i][p0][p1]|=g[i-2][p0-1][p1];
			if ((s[i-1]=='1'||s[i-2]=='1')&&p1>0) g[i][p0][p1]|=g[i-2][p0][p1-1];
		}
		if (s[i-1]=='0'&&p0>0) g[i][p0][p1]|=g[i-1][p0-1][p1+1];
		if (s[i-1]=='1'&&p1>0) g[i][p0][p1]|=g[i-1][p0+1][p1-1];
	}
	f[0][0][0]=1;
	for (int d=0;d<=n;d++) {
		for (int p0=0;p0<=d;p0++) for (int p1=0;p0+p1<=d;p1++) {
			int mt=d-p0-p1;
			if (g[n-mt][p0][p1]) {
				add(ans,f[d][p0][p1]);
			}
			if (d==n) continue;
			char t=s[n-1-mt];
			if (t=='0') add(f[d+1][p0][p1],f[d][p0][p1]);
			else add(f[d+1][p0+1][p1],f[d][p0][p1]);
			if (t=='1') add(f[d+1][p0][p1],f[d][p0][p1]);
			else add(f[d+1][p0][p1+1],f[d][p0][p1]);
		}
	}
	ans = sum(ans, Mod - 1);
	cout << ans << '\n';
	return 0;	 	
}

```