#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
void cksub(int&x,int y){x=sub(x,y);}
void ckmul(int&x,int y){x=mul(x,y);}
const int N=305;
bool ok[N][N][N];
int dp[N][N][N];
char s[N];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	ok[0][0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=n;~j;j--){
			for(int k=n;~k;k--){
				if(!ok[i][j][k])continue;
				if(j+k>=2&&j)ok[i][j-1][k]=1;
				if(j+k>=2&&k)ok[i][j][k-1]=1;
				if(s[i+1]=='1'||s[i+2]=='1')ok[i+2][j][k+1]=1;
				if(s[i+1]!='1'||s[i+2]!='1')ok[i+2][j+1][k]=1;
				if(s[i+1]=='1'&&k)ok[i+1][j][k]=1;
				if(s[i+1]=='1'&&j)ok[i+1][j-1][k+1]=1;
				if(s[i+1]!='1'&&k)ok[i+1][j+1][k-1]=1;
				if(s[i+1]!='1'&&j)ok[i+1][j][k]=1;
			}
		}
	}
	int ans=0;
	dp[n+1][0][0]=1;
	for(int i=n+1;i>=1;i--){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				if(ok[i-1][j][k]||ok[i][j+(s[i]!='1')][k+(s[i]=='1')])ckadd(ans,dp[i][j][k]);
				ckadd(dp[i-1][j][k],dp[i][j][k]);
				if(s[i-1]=='1')ckadd(dp[i][j+1][k],dp[i][j][k]);
				else ckadd(dp[i][j][k+1],dp[i][j][k]);
			}
		}
	}
	printf("%i\n",sub(ans,1));
	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>
using namespace std;
#define ll long long
const int mod=998244353;
int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
int sub(int x,int y){x-=y;return x<0?x+mod:x;}
int mul(int x,int y){return (ll)x*y%mod;}
void ckadd(int&x,int y){x=add(x,y);}
void cksub(int&x,int y){x=sub(x,y);}
void ckmul(int&x,int y){x=mul(x,y);}
const int N=305;
bool ok[N][N][N];
int dp[N][N][N];
char s[N];
int main(){
	scanf("%s",s+1);
	int n=strlen(s+1);
	ok[0][0][0]=1;
	for(int i=0;i<=n;i++){
		for(int j=n;~j;j--){
			for(int k=n;~k;k--){
				if(!ok[i][j][k])continue;
				if(j+k>=2&&j)ok[i][j-1][k]=1;
				if(j+k>=2&&k)ok[i][j][k-1]=1;
				if(s[i+1]=='1'||s[i+2]=='1')ok[i+2][j][k+1]=1;
				if(s[i+1]!='1'||s[i+2]!='1')ok[i+2][j+1][k]=1;
				if(s[i+1]=='1'&&k)ok[i+1][j][k]=1;
				if(s[i+1]=='1'&&j)ok[i+1][j-1][k+1]=1;
				if(s[i+1]!='1'&&k)ok[i+1][j+1][k-1]=1;
				if(s[i+1]!='1'&&j)ok[i+1][j][k]=1;
			}
		}
	}
	int ans=0;
	dp[n+1][0][0]=1;
	for(int i=n+1;i>=1;i--){
		for(int j=0;j<=n;j++){
			for(int k=0;k<=n;k++){
				if(ok[i-1][j][k]||ok[i][j+(s[i]!='1')][k+(s[i]=='1')])ckadd(ans,dp[i][j][k]);
				ckadd(dp[i-1][j][k],dp[i][j][k]);
				if(s[i-1]=='1')ckadd(dp[i][j+1][k],dp[i][j][k]);
				else ckadd(dp[i][j][k+1],dp[i][j][k]);
			}
		}
	}
	printf("%i\n",sub(ans,1));
	return 0;
}
```