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:
// Amsal Shoma Ro Gaedan Ye Amal Pasandidas !
#include <bits/stdc++.h>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'

using namespace std;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;

const ll Mod = 998244353;
const int N = 3e2 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;

ll dp[N][N][N];

bool b[N][N][N];
int ans[N][N], p0[N], p1[N];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	str s;
	cin >> s;
	int n = s.size();
	s = '!' + s;
	int c0 = 0, c1 = 0;
	for(auto c : s) c0 += (c == '0');
	for(auto c : s) c1 += (c == '1');
	memset(ans, -1, sizeof ans);

	for(int i = n - 1; i >= 0; i--) p0[i] = p0[i + 1] + (s[i + 1] == '0');
	for(int i = n - 1; i >= 0; i--) p1[i] = p1[i + 1] + (s[i + 1] == '1');

	b[0][0][0] = 1;
	for(int i = 0; i <= n; i++){
		for(int j = n; j >= 0; j--){
			for(int k = n; k >= 0; k--){
				if(!b[i][j][k]) continue;
				//cout << i << ' ' << j << ' ' << k << '\n';
				ans[c0 + j][c1 + k] = i;
				if(n - i + j + k < 2) continue;				
				
				if(j)
					b[i][j - 1][k] = 1;
				if(k)
					b[i][j][k - 1] = 1;
				if(j + k)
					b[i + 1][j][k] = 1;
				if(n - i >= 1){
					if(j)
						b[i + 1][j - 1 + (s[i + 1] == '0')][k + (s[i + 1] == '1')] = 1;
					if(k)
						b[i + 1][j + (s[i + 1] == '0')][k - 1 + (s[i + 1] == '1')] = 1;	
				}
				if(n - i >= 2){
					b[i + 2][j + (s[i + 1] == '0')][k + (s[i + 1] == '1')] = 1;
					b[i + 2][j + (s[i + 2] == '0')][k + (s[i + 2] == '1')] = 1;	
				}
			}
		}
		if(i < n){
			if(s[i + 1] == '0') c0 --;
			else c1 --;
		}
	}
	dp[n][0][0] = 1;
	for(int i = n; i >= 0; i--){
		for(int x = 0; x <= n; x++){
			for(int y = 0; y <= n; y++){
				if(i == n){
					if(x) dp[i][x][y] += dp[i][x - 1][y];
					if(y) dp[i][x][y] += dp[i][x][y - 1];
				} else {
					if(s[i + 1] == '0'){
						dp[i][x][y] = dp[i + 1][x][y] + (y ? dp[i][x][y - 1] : 0);
					} else {
						dp[i][x][y] = (x ? dp[i][x - 1][y] : 0) + dp[i + 1][x][y];
					}
				}
				dp[i][x][y] %= Mod;
			}
		}
	}
	ll res = 0;
	for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			if(ans[i][j] != -1){
				//cout << i << ' ' << j << ' ' << dp[ans[i][j]][i - p0[ans[i][j]]][j - p1[ans[i][j]]] << '\n';
				res += dp[ans[i][j]][i - p0[ans[i][j]]][j - p1[ans[i][j]]];
			}
		}
	}
	cout << res % Mod << '\n';
	return 0;
}