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:
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
	char c=getchar();bool f=0;x=0;
	while(!isdigit(c)) f|=c=='-',c=getchar();
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	if(f) x=-x;return x;
}
template<class t,class ...A> inline void read(t &x,A &...a){
	read(x);read(a...);
}
template<class t> inline void write(t x){
	if(x<0) putchar('-'),write(-x);
	else{if(x>9) write(x/10);putchar('0'+x%10);}
}

const int N=305,mod=998244353;
char s[N];
int f[N][N][N],n,ans;
bool ok[N][N][N];

signed main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	ok[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++) if(ok[i][j][k]){
		if(s[i+1]=='0'||s[i+2]=='0') ok[i+2][j+1][k]=1;
		if(s[i+1]=='1'||s[i+2]=='1') ok[i+2][j][k+1]=1;
		ok[i+1][j][k]=1;
		if(s[i+1]=='1'&&j) ok[i+1][j-1][k+1]=1;
		if(s[i+1]=='0'&&k) ok[i+1][j+1][k-1]=1; 
	}
	ok[n][0][0]=0;
	f[n][0][0]=1;
	for(int i=n;i;i--) for(int j=0;j<=i;j++) for(int k=0;j+k<=i;k++){
		(f[i-1][j][k]+=f[i][j][k])%=mod;
		if(s[i]=='0') (f[i][j][k+1]+=f[i][j][k])%=mod;
		if(s[i]=='1') (f[i][j+1][k]+=f[i][j][k])%=mod;
	}
	for(int i=0;i<=n;i++) for(int j=0;j<=i;j++) for(int k=0;j+k<=i;k++) (ans+=ok[i][j][k]*f[i][j][k])%=mod;
	write(ans);
}