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 rep(i,s,t) for(int i=s;i<=(t);++i)
#define dec(i,s,t) for(int i=s;i>=(t);--i)
using namespace std;
const int N=405,P=998244353;
void upd(int&a,int b){ a=a+b>=P?a+b-P:a+b; }
char s[N]; 
int ans,n,f[N][N][N],g[N][N][N]; 
int main(int argc,char *argv[]){
	scanf("%s",s+1); 
	n=strlen(s+1); 
	f[0][0][0]=1;
	rep(i,0,n)rep(j,0,i)rep(k,0,i)if(f[i][j][k]){
		int c0=(s[i+1]=='0')+(s[i+2]=='0'); 
		int c1=(s[i+1]=='1')+(s[i+2]=='1'); 
		if(i+2<=n&&c0)f[i+2][j+1][k]|=f[i][j][k]; 
		if(i+1<=n&&s[i+1]=='1'&&j>=1)f[i+1][j-1][k+1]|=f[i][j][k];
		if(i+2<=n&&c1)f[i+2][j][k+1]|=f[i][j][k];
		if(i+1<=n&&s[i+1]=='0'&&k>=1)f[i+1][j+1][k-1]|=f[i][j][k];
		f[i+1][j][k]|=f[i][j][k];
	}
	g[n+1][0][0]=1;
	dec(i,n+1,1)rep(j,0,n)rep(k,0,n-j){
		if(s[i-1]=='0'){
			upd(g[i-1][j][k],g[i][j][k]);
			upd(g[i][j][k+1],g[i][j][k]); 
		}else{
			upd(g[i][j+1][k],g[i][j][k]); 
			upd(g[i-1][j][k],g[i][j][k]); 
		}
		if(f[i-1][j][k]&&g[i][j][k])upd(ans,g[i][j][k]);
	}
	printf("%d\n",(ans-1+P)%P); 
	return 0; 
}