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;
namespace Base{
	# define mr make_pair
	typedef long long ll;
	typedef double db;
	const int inf = 0x3f3f3f3f, INF = 0x7fffffff;
	const ll  infll = 0x3f3f3f3f3f3f3f3fll, INFll = 0x7fffffffffffffffll;
	template<typename T> void read(T &x){
    	x = 0; int fh = 1; double num = 1.0; char ch = getchar();
		while (!isdigit(ch)){ if (ch == '-') fh = -1; ch = getchar(); }
		while (isdigit(ch)){ x = x * 10 + ch - '0'; ch = getchar(); }
	    if (ch == '.'){
	    	ch = getchar();
	    	while (isdigit(ch)){num /= 10; x = x + num * (ch - '0'); ch = getchar();}
		}
		x = x * fh;
	}
	template<typename T> void chmax(T &x, T y){x = x < y ? y : x;}
	template<typename T> void chmin(T &x, T y){x = x > y ? y : x;}
}
using namespace Base;

const int N = 310, P = 998244353;
int dp[N][N], f[N][N][N], n, ans;
vector <pair<int, int> > mp[N];
char s[N];
void join(int x, int y, int i){
	if (dp[x][y] != inf) return;
	dp[x][y] = i; 
	mp[i].push_back(mr(x, y));
}
int main(){
	scanf("\n%s", s + 1);
	n = strlen(s + 1);
	memset(dp, inf, sizeof(dp));
	dp[0][0] = 0;
	mp[0].push_back(mr(0, 0));
	for (int i = 2; i <= n; i++){
		for (unsigned j = 0; j < mp[i - 2].size(); j++){
			int x = mp[i - 2][j].first, y = mp[i - 2][j].second;
			if (s[i - 1] == '0' || s[i] == '0'){
				int tx = x + 1, ty = y;
				join(tx, ty, i);
			}
			if (s[i - 1] == '1' || s[i] == '1'){
				int tx = x, ty = y + 1;
				join(tx, ty, i);
			}
		}
		for (unsigned j = 0; j < mp[i - 1].size(); j++){
			int x = mp[i - 1][j].first, y = mp[i - 1][j].second;
			if (y > 0 && s[i] == '0'){
				int tx = x + 1, ty = y - 1;
				join(tx, ty, i);
			}
			if (x > 0 && s[i] == '1'){
				int tx = x - 1, ty = y + 1;
				join(tx, ty, i);
			}
		}
	}
	for (int i = n; i >= 0; i--)
		for (int j = n; j >= 0; j--)
			dp[i][j] = min(dp[i][j], min(dp[i + 1][j], dp[i][j + 1]));
	
	f[0][0][0] = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j <= i; j++)
			for (int k = 0; k <= i - j; k++){
				int t = i - j - k;
				if (dp[k][t] > n - j) continue;
				if (j > 0){
					if (s[n - j + 1] == '0'){
						f[j][k][t] = f[j - 1][k][t];
						if (t > 0) f[j][k][t] = (f[j][k][t] + f[j][k][t - 1]) % P;
					}
					else {
						f[j][k][t] = f[j - 1][k][t];
						if (k > 0) f[j][k][t] = (f[j][k][t] + f[j][k - 1][t]) % P;
					}
				}
				else {
					if (k > 0) f[j][k][t] = f[j][k - 1][t];
					if (t > 0) f[j][k][t] = (f[j][k][t] + f[j][k][t - 1]) % P;
				}
				if (j > 0){
					if (s[n - j + 1] == '0' && dp[k + 1][t] <= n - (j - 1)) continue;
					if (s[n - j + 1] == '1' && dp[k][t + 1] <= n - (j - 1)) continue;
				}
				ans = (ans + f[j][k][t]) % P;
			}
	}
	cout << ans << endl;
    return 0;
}