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

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;
const int N = 310;

typedef long long ll;
const int mod = 998244353;
inline int add(int a,int b){a+=b;return a>=mod?a-mod:a;}
inline int sub(int a,int b){a-=b;return a<0?a+mod:a;}
inline int mul(int a,int b){return 1ll*a*b%mod;}
inline int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=mul(a,a))if(b&1)ret=mul(ret,a);return ret;}
/* math */
int g[N][N][N],f[N][N][N],n;
// j zeros to add, k ones to add;
char s[N];

int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);reverse(s+1,s+n+1);
	s[n+1]='2';
	f[0][0][0]=g[0][0][0]=1;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			for(int k=0;j+k<=i;k++){
//				f[i][j][k]=add(f[i][j][k], g[i][j][k]);
				if(g[i][j][k]){
					int _d=i-j-k+1;
					int dir=s[_d]-'0';
					g[i+1][j][k]=add(g[i][j][k],g[i+1][j][k]);
					if(dir)g[i+1][j+1][k]=add(g[i+1][j+1][k],g[i][j][k]);
					else g[i+1][j][k+1]=add(g[i+1][j][k+1],g[i][j][k]);
				}
				/*-------*/
			}
		}
	}

	f[n][0][0]=1;
	for(int i=n-1;i;i--){
		for(int j=0;j<=i;j++){
			for(int k=0;j+k<=i;k++){
				int dir=s[i-j-k+1]-'0';
				int dir2=s[i-j-k+2]-'0';
//				assert(dir>=0&&dir<=1&&dir2>=0&&dir2<=1);
//				cerr << dir << " " << dir2 << endl;
				int nt[3];
				nt[0]=j,nt[1]=k,nt[2]=0;
				nt[0]++;
				if(nt[dir]){
					nt[dir]--;
					if(nt[dir2]&&(dir2==0||dir==0))nt[dir2]--;
				}
				f[i][j][k]|=f[i+1][nt[0]][nt[1]];
//				cerr << nt[0] << " " << nt[1] << ",";
				nt[0]=j,nt[1]=k;
				nt[1]++;
				if(nt[dir]){
					nt[dir]--;
					if(nt[dir2]&&(dir2==1||dir==1))nt[dir2]--;
				}
				f[i][j][k]|=f[i+1][nt[0]][nt[1]];
//				cerr << nt[0] << " " << nt[1] << endl;
//				cerr << i << " " << j << " " << k << "|" << f[i][j][k] << endl;
			}
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=i;j++)for(int k=0;k+j<=i;k++){
			if(f[i][j][k]){
//				cerr << i << " " << j << " " << k << " " << g[i][j][k] << endl;
				ans=add(ans, g[i][j][k]);
			}
		}
	}
	cout << ans << endl;
	return 0;
}