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>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,ll>
#define mk make_pair
#define pb push_back
#define eb emplace_back
#define ins insert
#define fi first
#define se second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=305,Mod=998244353;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
char s[MAXN];int n,a[MAXN],f[MAXN][MAXN][MAXN],g[MAXN][MAXN][MAXN];
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	scanf("%s",s+1),n=strlen(s+1);
	Rep(i,1,n)a[i]=s[i]^48;g[0][0][0]=1;
	Rep(i,1,n){
		Red(j,n,0)Red(k,n,0){
			g[i][j][k]|=g[i-1][j][k];
			if(a[i]==0)g[i][j][k]|=g[i][j][k+1];
			if(a[i]==1)g[i][j][k]|=g[i][j+1][k];
		}
		Rep(j,0,n)Rep(k,0,n)if(i>1){
			if((a[i]==0||a[i-1]==0)&&j)g[i][j][k]|=g[i-2][j-1][k];
			if((a[i]==0&&a[i-1]==0)&&j)g[i][j][k]|=g[i-1][j-1][k+1];
			if((a[i]==1||a[i-1]==1)&&k)g[i][j][k]|=g[i-2][j][k-1];
			if((a[i]==1&&a[i-1]==1)&&k)g[i][j][k]|=g[i-1][j+1][k-1];
		}
	}
	f[n+2][0][0]=1,a[0]=-1;
	Red(i,n+1,1){
		Rep(j,0,n)Rep(k,0,n)f[i][j][k]=f[i+1][j][k];
		if(a[i-1]!=1)Rep(j,0,n)Rep(k,1,n)f[i][j][k]=(f[i][j][k]+f[i][j][k-1])%Mod;
		if(a[i-1]!=0)Rep(j,1,n)Rep(k,0,n)f[i][j][k]=(f[i][j][k]+f[i][j-1][k])%Mod;
	}int c0=0,c1=0,ans=0;
	Rep(i,1,n+1)Rep(j,0,n)Rep(k,0,n)if(g[i-1][j][k])ans=(ans+f[i][j][k])%Mod;
	cout<<(ans-1+Mod)%Mod<<'\n';
	return 0;
}