#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=998244353;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=310;
char s[310];
int f[N][N][N],ans,n;
bool g[N][N][N];
void upd(int &a,int b) {
	a+=b; if (a>=mod) a-=mod;
}
int main() {
	scanf("%s",s);
	n=strlen(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]) {
				upd(ans,f[d][p0][p1]);
			}
			if (d==n) continue;
			char t=s[n-1-mt];
			if (t=='0') upd(f[d+1][p0][p1],f[d][p0][p1]);
			else upd(f[d+1][p0+1][p1],f[d][p0][p1]);
			if (t=='1') upd(f[d+1][p0][p1],f[d][p0][p1]);
			else upd(f[d+1][p0][p1+1],f[d][p0][p1]);
		}
	}
	printf("%lld\n",(ans+mod-1)%mod);
}
### 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 rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define fi first
#define se second
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=998244353;
ll powmod(ll a,ll b) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=310;
char s[310];
int f[N][N][N],ans,n;
bool g[N][N][N];
void upd(int &a,int b) {
	a+=b; if (a>=mod) a-=mod;
}
int main() {
	scanf("%s",s);
	n=strlen(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]) {
				upd(ans,f[d][p0][p1]);
			}
			if (d==n) continue;
			char t=s[n-1-mt];
			if (t=='0') upd(f[d+1][p0][p1],f[d][p0][p1]);
			else upd(f[d+1][p0+1][p1],f[d][p0][p1]);
			if (t=='1') upd(f[d+1][p0][p1],f[d][p0][p1]);
			else upd(f[d+1][p0][p1+1],f[d][p0][p1]);
		}
	}
	printf("%lld\n",(ans+mod-1)%mod);
}
```