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:
//Author: ReseeCher
#include<bits/stdc++.h>
#define LL long long
#define F(x,y,z) for(int x=y;x<=z;++x)
#define D(x,y,z) for(int x=y;x>=z;--x)
#define ckmax(a,b) (a)=max(a,b)
#define ckmin(a,b) (a)=min(a,b)
#define pb push_back
using namespace std;
const int N=305;
const int P=998244353;
LL R(){
    LL ans=0,f=1;char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) if (c=='-') f=-1;
    for(;c>='0'&&c<='9';c=getchar()) ans=ans*10+c-'0';
    return ans*f;
}
void Ad(LL &x,LL y){x=(x+y)%P;}
int n;
char s[N];
LL fn[N][N][N];
int g[N][N][N];
int main(){
	//freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	cin>>(s+1);n=strlen(s+1);
	fn[n][0][0]=1;
	D(i,n,1)F(j,0,n)F(k,0,n){
		Ad(fn[i-1][j][k],fn[i][j][k]);
		if(s[i]=='0')Ad(fn[i][j][k+1],fn[i][j][k]);
		else Ad(fn[i][j+1][k],fn[i][j][k]);
	}
	memset(g,-1,sizeof(g));
	g[0][0][0]=0;
	F(i,0,n)F(j,0,n)F(k,0,n){
		if(g[i][j][k]==-1)continue;
		if(s[i+1]=='0')ckmax(g[i+1][j+1][k],g[i][j][k]-1);
		else ckmax(g[i+1][j][k+1],g[i][j][k]-1);
		if(s[i+1]=='0'||s[i+2]=='0')ckmax(g[i+2][j+1][k],g[i][j][k]);
		if(s[i+1]=='1'||s[i+2]=='1')ckmax(g[i+2][j][k+1],g[i][j][k]);
		ckmax(g[i+2][j][k],g[i][j][k]+1);
	}
	F(i,0,n)D(j,n,0)D(k,n,0){
		if(i)ckmax(g[i][j][k],g[i-1][j][k]);
		ckmax(g[i][j][k],g[i][j+1][k]);
		ckmax(g[i][j][k],g[i][j][k+1]);
	}
	LL an=0;
	F(i,0,n)F(j,0,n)F(k,0,n)
		if(g[i][j][k]!=-1&&(n-i)+j+k!=0&&fn[i][j][k]){
			//printf("%d %d %d\n",i,j,k);
			Ad(an,fn[i][j][k]);
		}
	cout<<an<<'\n';
	return 0;
}