#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 303, mo = 998244353, inv2 =(mo+1)/2;
const ll MOD=7LL*mo*mo;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline void sub(int &x, int y){x=x-y>=0?x-y:x-y+mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
int res,n,f[N][N][N];char s[N];bool ok[N][N][N];
int main() {
	scanf("%s",s+1);n=strlen(s+1);
	f[0][0][0]=1;
	ok[0][0][0]=1;
	rep(i,1,n)rep(x,0,n)rep(y,0,n-x){
		ok[i][x][y]=ok[i-1][x][y];
		if(s[i]=='0'&&x)ok[i][x][y]|=ok[i-1][x-1][y+1];
		if(s[i]=='1'&&y)ok[i][x][y]|=ok[i-1][x+1][y-1];
		if(i>=2&&(s[i]=='0'||s[i-1]=='0')&&x)ok[i][x][y]|=ok[i-2][x-1][y];
		if(i>=2&&(s[i]=='1'||s[i-1]=='1')&&y)ok[i][x][y]|=ok[i-2][x][y-1];
	}
//	per(i,n-1,0)rep(x,0,n)rep(y,0,n-x)
//		ok[i][x][y]|=s[i+1]=='0'?ok[i+1][x+1][y]:ok[i+1][x][y+1];
	res=mo-1;
	rep(i,0,n)rep(x,0,n)rep(y,0,n-x)if(f[i][x][y]){
		if(ok[n-i][x][y])add(res,f[i][x][y]);//,cerr<<n-i<<' '<<x<<' '<<y<<' '<<f[i][x][y]<<endl;
		add(f[i+1][x][y],f[i][x][y]);
	//	if(i+x+y){
			if(s[n-i]=='1')add(f[i][x+1][y],f[i][x][y]);
			else add(f[i][x][y+1],f[i][x][y]);
	//	}
	}
	cout<<res;
	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<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> T gcd(T a, T b){return !b?a:gcd(b,a%b);}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 303, mo = 998244353, inv2 =(mo+1)/2;
const ll MOD=7LL*mo*mo;
inline void add(int &x, int y){x=x+y<mo?x+y:x+y-mo;}
inline void sub(int &x, int y){x=x-y>=0?x-y:x-y+mo;}
inline int power(int a, int n) {
	int res=1;
	while (n) {
		if (n&1) res=1LL*res*a%mo;
		a=1LL*a*a%mo; n>>=1;
	}
	return res;
}
int res,n,f[N][N][N];char s[N];bool ok[N][N][N];
int main() {
	scanf("%s",s+1);n=strlen(s+1);
	f[0][0][0]=1;
	ok[0][0][0]=1;
	rep(i,1,n)rep(x,0,n)rep(y,0,n-x){
		ok[i][x][y]=ok[i-1][x][y];
		if(s[i]=='0'&&x)ok[i][x][y]|=ok[i-1][x-1][y+1];
		if(s[i]=='1'&&y)ok[i][x][y]|=ok[i-1][x+1][y-1];
		if(i>=2&&(s[i]=='0'||s[i-1]=='0')&&x)ok[i][x][y]|=ok[i-2][x-1][y];
		if(i>=2&&(s[i]=='1'||s[i-1]=='1')&&y)ok[i][x][y]|=ok[i-2][x][y-1];
	}
//	per(i,n-1,0)rep(x,0,n)rep(y,0,n-x)
//		ok[i][x][y]|=s[i+1]=='0'?ok[i+1][x+1][y]:ok[i+1][x][y+1];
	res=mo-1;
	rep(i,0,n)rep(x,0,n)rep(y,0,n-x)if(f[i][x][y]){
		if(ok[n-i][x][y])add(res,f[i][x][y]);//,cerr<<n-i<<' '<<x<<' '<<y<<' '<<f[i][x][y]<<endl;
		add(f[i+1][x][y],f[i][x][y]);
	//	if(i+x+y){
			if(s[n-i]=='1')add(f[i][x+1][y],f[i][x][y]);
			else add(f[i][x][y+1],f[i][x][y]);
	//	}
	}
	cout<<res;
	return 0;
}

```