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 pb emplace_back
using namespace std;
using ll = long long;
const int maxn = 302, p = 998244353;
void add(int &v, int val) {
	v += val - p;
	v += (v>>31) & p;
}
int dp[maxn][maxn][maxn], n, c0, c1, pf1[maxn][maxn<<1][maxn], pf2[maxn][maxn][maxn];
bool can[maxn][maxn][maxn];
int pc0[maxn], pc1[maxn], suf1[maxn], suf0[maxn];
char w[maxn];
int res;
void makepf(int x) {
	for (int i = 1;i < n+n;++i)
		for (int j = 0;j < n;++j) {
			pf1[x][i][j] = dp[x][i][j];
			add( pf1[x][i][j], pf1[x][i-1][j+1] );
		}
	for (int i = 1;i < n;++i)
		for (int j = 0;j < n;++j) {
			pf2[x][i][j] = dp[x][i][j];
			add( pf2[x][i][j], pf2[x][i-1][j] );
		}
}
#define G(V, i, j, k) (min({i,j,k}) < 0 ? 0 : V[i][j][k])
#define GC(V, i) ((i) < 0 ? 0 : V[i])
void getdp() {
	dp[n][0][0] = 1;
	for (int i = n;i >= 0;--i) 
		for (int j = 0;j <= n;++j)
			for (int k = 0;k <= n;++k) if (dp[i][j][k]) {
				char W = (i>0? w[i-1] : ';');
				if (W != '0')
					add(dp[i][j+1][k], dp[i][j][k]);
				if (W != '1')
					add(dp[i][j][k+1], dp[i][j][k]);
				if (i)
					add(dp[i-1][ j ][ k ], dp[i][j][k]);
			}
	for (int i = 1;i <= n;++i)
		for (int j = 0;j <= n;++j)
			for (int k = 0;k <= n;++k) {
		//		if (can[i-1][j][k])
		//			cerr << i-1 << ' ' << j << ' '<< k << " dp " << dp[i][j][k] << '\n';
				if (dp[i][j][k] && can[i-1][j][k])
					add(res, dp[i][j][k]);
			}
}

void solve() {
	for (int i = n-1;i >= 0;--i) {
		suf1[i] = suf1[i+1] + (w[i] == '1');
		suf0[i] = suf0[i+1] + (w[i] == '0');
	}
	{
		int x = w[0] == '0', y = w[1] == '0';
		can[0][0][0] = true;
		can[1][x || y][0] = true;
		can[1][0][!x || !y] = true;
		for (int i = 0;i <= n;++i) 
			for (int j = 0;j <= i+1;++j)
				for (int k = 0;k <= i+1;++k) if (can[i][j][k]) {
					int x = w[i+1] == '0', y = w[i+2] == '0';
					int q = w[i+1] == '1', e = w[i+2] == '1';
					can[i+2][j + (x || y)][k] = true;
					can[i+2][j][k + (q || e)] = true;
					can[i+1][j][k] = true;
					if (j) can[i+1][j-1][k + q] = true;
					if (k) can[i+1][j + x][k-1] = true;
				}
	}
	
	getdp();
//	dp[n][n][0] = 1;
//	makepf(n);
//	for (int i = n-1;i >= 0;--i) {
//		for (int j = i;j >= 0;--j) {
//			for (int k = 0;k <= n;++k) {
//				int &A = dp[i][j][k];
//				int nc0 = k, nc1 = n - j - k;
//				int ec0 = nc0 - suf0[i], ec1 = nc1 - suf1[i];
//				if (nc0 > c0 || nc1 > c1 || w[i] == '0' && !k)
//					continue;
//				if (w[i] == '1') {
//					int lx = j+1, ly = k, rx = j+k+1, ry = 0;
//					for (int d = 0;d <= k && j+d+1 <= n;++d)
//						add(A, dp[i+1][j+d+1][k-d]);
////					add(A, pf1[i+1][rx][ry]);
////					add(A, p - G(pf1, i+1, lx-1, ly+1));
//				}
//				else {
//					int lx = j, rx = n;
//					assert(k);
//					for (int d = 0;d + j + 1 <= n;++d)
//						add(A, dp[i+1][j+d+1][k-1]);
////					add(A, pf2[i+1][rx][k-1]);
////					add(A, p - G(pf2, i+1, lx-1, k-1));
//				}
//				//printf("dp[%d][%d][%d] : %d len : %d\n", i, j, k, dp[i][j][k], nc0 + nc1);
//			}
//		}
//		//puts("------");
//		makepf(i);
//	}
//	for (int i = 0;i <= n;++i)
//		for (int j = 0;j <= i;++j)
//			for (int k = 0;k <= n;++k) if (dp[i][j][k]) {
//				int &A = dp[i][j][k];
//				int nc0 = k, nc1 = n - j - k;
//				int ec0 = nc0 - suf0[i], ec1 = nc1 - suf1[i];
//				if (ec0 > GC(pc0, i-1) || ec1 > GC(pc1, i-1)) 
//					continue;
////				int nc0 = k, nc1 = n - j - k, nowlen = n - j, uplen = n - i, gar = nowlen - uplen, coda = n - nowlen;
////				if (coda < gar) continue;
////				int ex = min(coda - gar >> 1, i==0?0: w[i-1] == '0' ? c1 - nc1 : c0 - nc0);
////				//ex = max(0, ex);
////				add(res, dp[i][j][k] * (ex+1) % p);
////				printf("dp[%d][%d][%d] : %d len : %d ex : %d\n", i, j, k, dp[i][j][k], nc0 + nc1, ex);
//			}
//	add(res, p-1);

}
signed main(){
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> w;
	n = strlen(w);
	for (int i = 0;i < n;++i)
		c0 += w[i] == '0', c1 += w[i] == '1';
	solve();
	cout << res << '\n'; 
}