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

typedef long long LL;

const int N=300,mod=998244353;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n;

void into(){
  scanf("%s",s+1);
  n=strlen(s+1);
}

int dp[N+9][N+9][N+9];

void Get_dp(){
  dp[n][0][0]=1;
  for (int i=n;i>=1;--i)
	for (int j=0;j<i;++j)
	  for (int k=0;j+k<i;++k){
		dp[i-1][j][k]=dp[i][j][k];
		s[i]=='0'?sadd(dp[i][j][k+1],dp[i][j][k]):sadd(dp[i][j+1][k],dp[i][j][k]);
	  }
}

int f[N+9][N+9][N+9];

void Get_f(){
  for (int i=0;i<=n;++i)
	for (int j=0;j<=n+1;++j)
	  for (int k=0;k<=n+1;++k) f[i][j][k]=-1;
  f[0][0][0]=0;
  for (int i=0;i<n;++i)
	for (int j=0;j<=i>>1;++j)
	  for (int k=0;j+k<=i>>1;++k){
		if (f[i][j][k]==-1) continue;
		s[i+1]=='0'?f[i+1][j+1][k]=max(f[i+1][j+1][k],f[i][j][k]-1):f[i+1][j][k+1]=max(f[i+1][j][k+1],f[i][j][k]-1);
		if (i+2>n) continue;
		f[i+2][j][k]=max(f[i+2][j][k],f[i][j][k]+1);
		if (s[i+1]=='0'||s[i+2]=='0') f[i+2][j+1][k]=max(f[i+2][j+1][k],f[i][j][k]);
		if (s[i+1]=='1'||s[i+2]=='1') f[i+2][j][k+1]=max(f[i+2][j][k+1],f[i][j][k]);
	  }
  for (int i=0;i<=n;++i)
	for (int j=n;j>=0;--j)
	  for (int k=n;k>=0;--k){
		f[i][j][k]=max(f[i][j][k],max(f[i][j][k+1],f[i][j+1][k]));
		if (i) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
	  }
}

int ans;

void Get_ans(){
  for (int i=0;i<=n;++i)
	for (int j=0;j<=i;++j)
	  for (int k=0;j+k<=i;++k)
		if (f[i][j][k]>=0) sadd(ans,dp[i][j][k]);
}

void work(){
  Get_dp();
  Get_f();
  Get_ans();
}

void outo(){
  printf("%d\n",sub(ans,1));
}

int main(){
  into();
  work();
  outo();
  return 0;
}
### Prompt

Please create a solution in Cpp 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;

typedef long long LL;

const int N=300,mod=998244353;

int add(int a,int b,int p=mod){return a+b>=p?a+b-p:a+b;}
int sub(int a,int b,int p=mod){return a-b<0?a-b+p:a-b;}
int mul(int a,int b,int p=mod){return (LL)a*b%p;}
void sadd(int &a,int b,int p=mod){a=add(a,b,p);}
void ssub(int &a,int b,int p=mod){a=sub(a,b,p);}
void smul(int &a,int b,int p=mod){a=mul(a,b,p);}

char s[N+9];
int n;

void into(){
  scanf("%s",s+1);
  n=strlen(s+1);
}

int dp[N+9][N+9][N+9];

void Get_dp(){
  dp[n][0][0]=1;
  for (int i=n;i>=1;--i)
	for (int j=0;j<i;++j)
	  for (int k=0;j+k<i;++k){
		dp[i-1][j][k]=dp[i][j][k];
		s[i]=='0'?sadd(dp[i][j][k+1],dp[i][j][k]):sadd(dp[i][j+1][k],dp[i][j][k]);
	  }
}

int f[N+9][N+9][N+9];

void Get_f(){
  for (int i=0;i<=n;++i)
	for (int j=0;j<=n+1;++j)
	  for (int k=0;k<=n+1;++k) f[i][j][k]=-1;
  f[0][0][0]=0;
  for (int i=0;i<n;++i)
	for (int j=0;j<=i>>1;++j)
	  for (int k=0;j+k<=i>>1;++k){
		if (f[i][j][k]==-1) continue;
		s[i+1]=='0'?f[i+1][j+1][k]=max(f[i+1][j+1][k],f[i][j][k]-1):f[i+1][j][k+1]=max(f[i+1][j][k+1],f[i][j][k]-1);
		if (i+2>n) continue;
		f[i+2][j][k]=max(f[i+2][j][k],f[i][j][k]+1);
		if (s[i+1]=='0'||s[i+2]=='0') f[i+2][j+1][k]=max(f[i+2][j+1][k],f[i][j][k]);
		if (s[i+1]=='1'||s[i+2]=='1') f[i+2][j][k+1]=max(f[i+2][j][k+1],f[i][j][k]);
	  }
  for (int i=0;i<=n;++i)
	for (int j=n;j>=0;--j)
	  for (int k=n;k>=0;--k){
		f[i][j][k]=max(f[i][j][k],max(f[i][j][k+1],f[i][j+1][k]));
		if (i) f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);
	  }
}

int ans;

void Get_ans(){
  for (int i=0;i<=n;++i)
	for (int j=0;j<=i;++j)
	  for (int k=0;j+k<=i;++k)
		if (f[i][j][k]>=0) sadd(ans,dp[i][j][k]);
}

void work(){
  Get_dp();
  Get_f();
  Get_ans();
}

void outo(){
  printf("%d\n",sub(ans,1));
}

int main(){
  into();
  work();
  outo();
  return 0;
}
```