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 ll long long
#define sd(x) scanf("%d", &(x))
#define pii pair<int, int>
#define F first
#define S second
#define all(c) ((c).begin()), ((c).end())
#define sz(x) ((int)(x).size())
#define ld long double

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<", "<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	for(int i = 0;i < (int)v.size(); i++){
		if(i)os<<", ";
		os<<v[i];
	}
	os<<"}";
	return os;
}

#ifdef LOCAL
#define cerr cout
#else
#endif

#define TRACE

#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif
const int N = 305;
const int mod = 998244353;

inline int add(int x, int y){ x += y; if(x >= mod) x -= mod; return x;}
inline int sub(int x, int y){ x -= y; if(x < 0) x += mod; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % mod;}
inline int powr(int a, ll b){
	int x = 1 % mod;
	while(b){
		if(b & 1) x = mul(x, a);
		a = mul(a, a);
		b >>= 1;
	}
	return x;
}
inline int inv(int a){ return powr(a, mod - 2);}

int dp[N][N][N];
int dp2[3][N][N][N];
int possible[N][N][N];
int pref[2][N];
int main(){
	string s; cin >> s;
	int n = s.length();
    // int n = (int) s.size();
  vector<vector<vector<bool>>> can(n + 1, vector<vector<bool>>(n + 1, vector<bool>(n + 1, false)));
	// trace(n);
  can[0][0][0] = true;
  for (int i = 0; i <= n; i++) {
    for (int k0 = n; k0 >= 0; k0--) {
      for (int k1 = n; k1 >= 0; k1--) {
        if (!can[i][k0][k1]) {
          continue;
        }
        // both from string
        if (i + 2 <= n) {
          if (s[i] == '0' || s[i + 1] == '0') {
            can[i + 2][k0 + 1][k1] = true;
          }
          if (s[i] == '1' || s[i + 1] == '1') {
            can[i + 2][k0][k1 + 1] = true;
          }
        }
        // both from pocket
        if (k0 > 0 && k0 + k1 >= 2) {
          can[i][k0 - 1][k1] = true;
        }
        if (k1 > 0 && k0 + k1 >= 2) {
          can[i][k0][k1 - 1] = true;
        }
        // one from string, one from pocket, erase from string
        if (i + 1 <= n && k0 + k1 >= 1) {
          can[i + 1][k0][k1] = true;
        }
        // one from string, one from pocket, erase from pocket
        if (i + 1 <= n && k0 > 0) {
          if (s[i] == '0') {
            can[i + 1][k0][k1] = true;
          } else {
            can[i + 1][k0 - 1][k1 + 1] = true;
          }
        }
        if (i + 1 <= n && k1 > 0) {
          if (s[i] == '0') {
            can[i + 1][k0 + 1][k1 - 1] = true;
          } else {
            can[i + 1][k0][k1] = true;
          }
        }
      }
    }
  }
	// trace()s
	s = "$" + s;
	dp2[2][0][0][0] = possible[0][0][0] = 1;
	for(int i = 1; i <= n; i++){
		pref[0][i] = pref[0][i - 1];
		pref[1][i] = pref[1][i - 1];
		int other = s[i] - '0';
		pref[other][i]++;
		for(int n0 = 0; n0 <= i; n0++) for(int n1 = 0; n1 <= i; n1++){
			for(int old = 0; old < 2; old++) if(dp2[old][i - 1][n0][n1]){
				int h[2] = {n0, n1};
				dp2[old][i][h[0]][h[1]] = 1; // throw other away
				dp2[other][i][h[0]][h[1]] = 1; // throw old away
				h[other]++;
				dp2[2][i][h[0]][h[1]] = 1;// throw old away, other to right
				h[other]--; h[old]++;
				dp2[2][i][h[0]][h[1]] = 1; // throw other away, old to right
			}

			// old = 2
			if(dp2[2][i - 1][n0][n1]) dp2[other][i][n0][n1] = 1;
		}
		for(int n0 = 0; n0 <= n; n0++) for(int n1 = 0; n1 <= n; n1++){
			possible[i][n0][n1] |= dp2[2][i][n0][n1];
            // if(!(can[i][n0][n1] == possible[i][n0][n1]))
            // trace(i, n0, n1, can[i][n0][n1]);
            // assert(can[i][n0][n1] == possible[i][n0][n1]);
            if(can[i - 1][n0][n1]) can[i][n0][n1] = true;
			// possible[i][n0][n1] |= possible[i - 1][n0][n1];
		}
		// 	possible[i][n0][n1] |= dp2[curr][i][n0][n1];
	}

	dp[0][0][0] = 1;

	int ans = 0;

	for(int n0 = 0; n0 <= n; n0++) for(int n1 = 0; n1 <= n; n1++){
		for(int now = 0; now < 2; now++){
			int nn0 = n0, nn1 = n1;
			if(now==0) nn0++;
			if(now==1) nn1++;
			for(int k = 0; k <= n; k++){
				int num_0 = n0 - (pref[0][n] - pref[0][n - k]);
				int num_1 = n1 - (pref[1][n] - pref[1][n - k]);
				// maximum suffix that exists as a subsequence ?
				int kk = k;
				if(s[n - k] - '0'== now){
					kk++;
				}
				
				dp[nn0][nn1][kk] = add(dp[nn0][nn1][kk], dp[n0][n1][k]);
				
				if(now == 0 && num_0 >= 0&& num_1 >= 0 && n0 + n1 >= 1){
					
					if(can[n - k][num_0][num_1]){
						ans = add(ans, dp[n0][n1][k]);
					}
				}
			}
		}
	}
	cout << ans << endl;
}