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 ull unsigned ll
#define uint unsigned
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
#define PB push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
#define debug puts("wzpakking")
#define y1 ysghysgsygsh
#define all(v) v.begin(),v.end()
using namespace std;
const int mo=998244353;
const int N=305;
char s[N];
int n,s0,s1;
int f[N][N][N];
int g[N][N][N];
void UPD(int &x,int y){
	(x+=y)>=mo?x-=mo:233;
}
void initF(){
	f[0][0][0]=1;
	For(i,0,n-1) For(v1,0,s0) For(v2,0,s1){
		if (!f[i][v1][v2]) continue;
		if (i+2<=n){
			if (s[i+1]=='0'||s[i+2]=='0') f[i+2][v1+1][v2]=1;
			if (s[i+1]=='1'||s[i+2]=='1') f[i+2][v1][v2+1]=1;
		}
		if (v1||v2) f[i+1][v1][v2]=1;
		if (s[i+1]=='0'&&v2) f[i+1][v1+1][v2-1]=1;
		if (s[i+1]=='1'&&v1) f[i+1][v1-1][v2+1]=1;
	}
	For(i,1,n) For(v1,0,s0) For(v2,0,s1)
		if (f[i][v1][v2]){
			if (v1&&s[i]=='0') f[i-1][v1-1][v2]=0;
			if (v2&&s[i]=='1') f[i-1][v1][v2-1]=0;
		}
}
void initG(){
	g[n+1][0][0]=1;
	Rep(i,n+1,1) For(v1,0,s0) For(v2,0,s1){
		if (!g[i][v1][v2]) continue;
		int v=g[i][v1][v2];
		if (s[i-1]!='0') UPD(g[i][v1+1][v2],v);
		if (s[i-1]!='1') UPD(g[i][v1][v2+1],v);
		UPD(g[i-1][v1][v2],v);
	}
	For(i,1,n+1){
		Rep(v1,s0,0) Rep(v2,s1,0){
			int v=g[i][v1][v2];
			if (s[i-1]!='0') UPD(g[i][v1+1][v2],mo-v);
			if (s[i-1]!='1') UPD(g[i][v1][v2+1],mo-v);
		}
		For(v1,0,s0) For(v2,0,s1){
			int v=g[i][v1][v2];
			UPD(g[i][v1+1][v2],v);
			UPD(g[i][v1][v2+1],v);
		}
	}
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	For(i,1,n) s[i]=='0'?++s0:++s1;
	initF();
	initG();
	int ans=0;
	For(i,0,n) For(v1,0,s0) For(v2,0,s1)
		if (f[i][v1][v2]) UPD(ans,g[i+1][v1][v2]);
	cout<<ans<<endl;
}