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>
using namespace std;
#define int long long
const int mod=998244353;
int f[305][305][305];bool flag[305][305][305];
void add(int &x,int y){
	x=(x+y)%mod;
}
char s[305];
signed main(){
	cin>>(s+1);
	int n=strlen(s+1);
	f[n][0][0]=1;
	for(int i=n;i>=1;--i)
		for(int j=0;j<=i;++j)
			for(int k=0;j+k<=i;++k)
				if(f[i][j][k]){
					add(f[i-1][j][k],f[i][j][k]);
					if(s[i]=='0') add(f[i][j][k+1],f[i][j][k]);
					else add(f[i][j+1][k],f[i][j][k]);
				}
	for(int i=0;i<n;++i){
		flag[i][0][0]=1;
		for(int j=0;j<=i;++j)
			for(int k=0;j+k<=i;++k)
				if(flag[i][j][k]){
					flag[i+1][j][k]=1;
					if(s[i+1]=='0' || s[i+2]=='0') flag[i+2][j+1][k]=1;
					if(s[i+1]=='1' || s[i+2]=='1') flag[i+2][j][k+1]=1;
					if(s[i+1]=='0' && k) flag[i+1][j+1][k-1]=1;
					if(s[i+1]=='1' && j) flag[i+1][j-1][k+1]=1;
				}
	}
	flag[n][0][0]=0;
	int ans=0;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=i;++j)
			for(int k=0;j+k<=i;++k)
				if(flag[i][j][k]) add(ans,f[i][j][k]);
	cout<<ans;
	return 0;
}