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 N 310
#define mo 998244353
using namespace std;
string s;
ll jie[N],nj[N],dp[N][N][N],f[N][2],ans,n;
ll po(ll x,ll y){ll z=1;while (y){if (y%2)z=x*z%mo;x=x*x%mo;y/=2;}return z;}
ll C(ll x,ll y){if (x==-1&&y==0)return 1;if (x<y)return 0;return (jie[x]*nj[y]%mo)*nj[x-y]%mo;}
int main(){
	cin>>s;n=s.length();
	jie[0]=1;for (int i=1;i<=n;i++)jie[i]=jie[i-1]*i%mo;
	nj[n]=po(jie[n],mo-2);for (int i=n-1;i>=0;i--)nj[i]=nj[i+1]*(i+1)%mo;
	dp[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 (dp[i][j][k]){
					dp[i+1][j][k]=1;
					if (s[i]=='0'||s[i+1]=='0')dp[i+2][j+1][k]=1;
					if (s[i]=='1'||s[i+1]=='1')dp[i+2][j][k+1]=1;
					if (s[i]=='0'&&k)dp[i+1][j+1][k-1]=1;
					if (s[i]=='1'&&j)dp[i+1][j-1][k+1]=1;
				}
			}
		}
	}
	for (int i=n;i>=1;i--){f[i][0]=f[i+1][0];f[i][1]=f[i+1][1];f[i][s[i-1]-'0']++;}
	for (int i=0;i<=n;i++){
		for (int j=0;j<=i;j++){
			for (int k=0;k+j<=i;k++){
				if (dp[i][j][k]){
					ans=(ans+C(f[i][0]+k-1,k)*C(f[i][1]+j-1,j))%mo;
				}
			}
		}
	}
	cout<<(ans+mo-1)%mo<<endl;
	return 0;
}