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>
const int N=305,mo=998244353;
inline void add(int&a,const int&b){a+=b-mo;a+=a>>31&mo;}
int n,i,j,k,f[N][N][N],x,ans=mo-1;
char c[N];
bool g[N][N][N];
int main(){
	scanf("%s",c+1);n=strlen(c+1);
	f[0][0][0]=1;
	for(i=0;i<=n;++i)for(j=0;j<=n;++j)for(k=0;k<=n;++k){
		x=f[i][j][k];
		add(f[i+1][j][k],x);
		add(c[n-i]=='1'?f[i][j+1][k]:f[i][j][k+1],x);
	}
	g[0][0][0]=1;
	for(i=0;i<=n;++i)for(j=n;j>=0;--j)for(k=n;k>=0;--k)if(g[i][j][k]){
		if(j)g[i][j-1][k]=1;if(k)g[i][j][k-1]=1;
		g[i+1][j][k]=1;
		if(c[i+1]=='0' && k)g[i+1][j+1][k-1]=1;
		if(c[i+1]=='1' && j)g[i+1][j-1][k+1]=1;
		if(i+2<=n){
			if(c[i+1]=='0' || c[i+2]=='0')g[i+2][j+1][k]=1;
			if(c[i+1]=='1' || c[i+2]=='1')g[i+2][j][k+1]=1;
		}
		add(ans,f[n-i][j][k]);
	}
	printf("%d\n",ans);
}