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:
//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 300 + 10;
const ll MOD = 998244353;
const ll INF = 1000000010;
const ll LOG = 25;

bool DP[N][N][N];
int dp[N][N][N], mark[N][N][N], n, ps[N];
string s;

int32_t main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> s;
	if (s.size() == 1) return cout << 1, 0;
//	cout << s << endl;
	n = s.size();
	DP[0][0][0] = 1;
	for (int k = 1; k <= n; k++){
		ps[k] = ps[k - 1] + (s[k - 1] == '1');
		if (k == 1) continue;
		for (int j = k; j >= 0; j--){
			for (int i = k; i >= 0; i--){
				if (j + i == 0) continue;
				if (s[k - 1] == '0'){
					DP[i][j][k] |= DP[i][j][k - 1];
					DP[i][j][k] |= DP[i + 1][j][k] | DP[i][j + 1][k];
					if (i != 0) DP[i][j][k] |=  DP[i - 1][j + 1][k - 1];
				}else{
					DP[i][j][k] |= DP[i][j][k - 1];
					DP[i][j][k] |= DP[i + 1][j][k] | DP[i][j + 1][k];
					if (j != 0) DP[i][j][k] |=  DP[i + 1][j - 1][k - 1];
				}
				if ((s[k - 1] == '1' || s[k - 2] == '1') && (j != 0)) DP[i][j][k] |= DP[i][j - 1][k - 2];
				if ((s[k - 1] == '0' || s[k - 2] == '0') && (i != 0)) DP[i][j][k] |= DP[i - 1][j][k - 2];
//				cout << i << ' '  << j << ' ' <<k<<' '<< DP[i][j][k] << '\n';
			}
		}
	}
	dp[0][0][0] = 1;
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++){
		if (s[n - k - 1] == '0') dp[i + 1][j][k + 1] = (dp[i + 1][j][k + 1] + dp[i][j][k]) % MOD, dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i][j][k]) % MOD;
		else dp[i][j + 1][k + 1] = (dp[i][j + 1][k + 1] + dp[i][j][k]) % MOD, dp[i + 1][j][k] = (dp[i + 1][j][k] + dp[i][j][k]) % MOD;
//		cout << i << ' ' << j << ' ' <<k << ' '<< dp[i][j][k] <<'\n';
	}
	for (int k = 0; k <= n; k++)for (int i = 0; i <= k; i++)for (int j = 0; j <= n; j++){
		if (k == 1) continue;
		if (DP[i][j][k]){
			int x = i + (n - k - ps[n] + ps[k]);
			int y = (j + ps[n] - ps[k]);
			mark[x][y][n - k] = 1;
		}
	}
	int ans = 0;
	for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++)	for (int k = 0; k <= n; k++){
		if (k != 0) mark[i][j][k] |= mark[i][j][k - 1];
		if (mark[i][j][k]) ans = (ans + dp[i][j][k]) % MOD;
	}
	cout << ans;








	return 0;
}