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;
typedef long long ll;
const int N=305,p=998244353;
int read(){
	int f=1,g=0;
	char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int qpow (int x,int k){
	int t=1;
	for (;k;k>>=1){
		if (k&1) t=(ll)t*x%p;
		x=(ll)x*x%p;
	}
	return t;
}
int n,ans,f[N][N][N],g[N][N][N];
char ch[N];
void check(int &x,int y){if((x+=y)>=p) x-=p;}
void chkmax(int &x,int y){if (x<y) x=y;}
int main(){
//	freopen("a.in","r",stdin);
	scanf(" %s",ch+1);
	n=strlen(ch+1);
	if (n==1){puts("1");return 0;}
	memset(f,0xC0,sizeof(f));
	f[0][0][0]=0;
	for (int i=0;i<n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++){
		chkmax(f[i+1][j][k],f[i][j][k]);
		if (j){
			if (ch[i+1]=='0') chkmax(f[i+1][j-1][k+1],f[i][j][k]);
			else chkmax(f[i+1][j-1][k],f[i][j][k]+1);
		}
		if (i+2<=n){
			if ((ch[i+1]=='0')||(ch[i+2]=='0')) chkmax(f[i+2][j][k+1],f[i][j][k]);
			if ((ch[i+1]=='1')||(ch[i+2]=='1')) chkmax(f[i+2][j][k],f[i][j][k]+1);
			chkmax(f[i+2][j+1][k],f[i][j][k]);
		}
	}
	for (int i=0;i<=n;i++)
	for (int j=0;j<=i;j++)
	for (int k=0;k<=i;k++)
	chkmax(f[i][0][k],f[i][j][k]);
	
	g[n+1][0][0]=1;ans=p-1;
	for (int i=n+1;i;i--)
	for (int j=0;j<i;j++)
	for (int k=0;j+k<i;k++){
		if (f[i-1][0][j]>=k) check(ans,g[i][j][k]);
		if (i==1) continue;
		check(g[i-1][j][k],g[i][j][k]);
		if (ch[i-1]=='0') check(g[i][j][k+1],g[i][j][k]);
		else check(g[i][j+1][k],g[i][j][k]);
	}
	printf("%d\n",ans);
	return 0;
}