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 ld long double
#define ll long long
#define st first
#define nd second
#define mp make_pair
#define pii pair<int, int>
#define vi vector<int>
#define pb push_back
using namespace std;
const ll mod = 998244353;
const int N = 305;
int n;
string s, t;
ll dp[N][N][N];
bool p[N][N][N], ign[N][N][N];
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>s;
	n = s.size();
	if(n==1) {
		cout<<1;
		return 0;
	}
	t = s;
	reverse(t.begin(), t.end());
	for(int i=0; i<=n; ++i) {
		for(int j=n; j>=0; --j) {
			for(int k=n; k>=0; --k) {
				if(i==0) {
					if(j==0 && k==0) p[i][j][k]=1;
					continue;
				}
				if(i==1) continue;
				if((s[i-2] == '0' || s[i-1] == '0') && j != 0) {
					p[i][j][k] = p[i][j][k] | p[i-2][j-1][k];
				}
				if((s[i-2] == '1' || s[i-1] == '1') && k != 0) {
					p[i][j][k] = p[i][j][k] | p[i-2][j][k-1];
				}
				p[i][j][k] = p[i][j][k] | p[i-1][j][k];
				if((s[i-1] == '0') && j != 0) {
					p[i][j][k] = p[i][j][k] | p[i-1][j-1][k+1];
				}
				if((s[i-1] == '1') && k != 0){
					p[i][j][k] = p[i][j][k] | p[i-1][j+1][k-1];
				}
				p[i][j][k] = p[i][j][k] | p[i][j+1][k];
				p[i][j][k] = p[i][j][k] | p[i][j][k+1];
				
			}
		}
	}
	for(int i=0; i<=n; ++i) {
		for(int j=0; j<=n; ++j) {
			for(int k=0; k<=n; ++k) {
				if(i==0 && j==0 && k==0) {
					dp[i][j][k] = 1;
					continue;
				}
				if(i==0) {
					dp[i][j][k] = (((j==0)?0LL:dp[i][j-1][k]) + ((k==0)?0LL:dp[i][j][k-1])) % mod;	
					continue;
				}
				dp[i][j][k] = dp[i-1][j][k];
				if(t[i-1] == '0' && k != 0) dp[i][j][k] = (dp[i][j][k] + dp[i][j][k-1]) % mod;
				if(t[i-1] == '1' && j != 0) dp[i][j][k] = (dp[i][j][k] + dp[i][j-1][k]) % mod;
				if(t[i-1] == '0' && (p[n-(i-1)][j+1][k] || ign[i-1][j+1][k])) {
					ign[i][j][k]=1;
				}
				if(t[i-1]=='1' && (p[n-(i-1)][j][k+1] || ign[i-1][j][k+1])) {
					ign[i][j][k]=1;
				}
			}
		}
	}

	ll ans = 0;
	for(int i=0; i<=n; ++i) {
		for(int j=0; j<=n; ++j) {
			for(int k=0; k<=n; ++k) {
				if(!ign[i][j][k] && p[n-i][j][k]) ans = (ans + dp[i][j][k]) % mod;
				//if(p[n-i][j][k] && !ign[i][j][k]) {
				//	cout<<i<<' '<<j<<' '<<k<<": "<<dp[i][j][k]<<'\n';
				//}
			}
		}
	}
	cout<<(ans-1+mod)%mod;
}