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:
//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define maxn 305 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
int n, a;
char inp[maxn];
int dp[maxn][maxn][maxn]; // 长度 还没匹配啥 几个1 
int fl[maxn][maxn][maxn]; // 从 j 到 n， 提取出 x 个 1 y 个 b 
int mx[maxn][maxn];
int ed[maxn];
int main() {
	scanf("%s", inp + 1);
	int l = strlen(inp + 1);
	for (int i = l; i >= 1; i--) {
		ed[i] = ed[i + 1];
		if (inp[i] == '1') ed[i]++;
	}
	dp[0][l][0] = 1;
	for (int i = 0; i <= l; i++)
		for (int j = 0; j <= l; j++)
			for (int k = 0; k <= i; k++)
				for (int s = 0; s < 2; s++) {
					int ei = i + 1, ej = j, ek = k;
					if (s == 1) ek++;
					if (s == inp[j] - '0') ej--;
					dp[ei][ej][ek] = (dp[ei][ej][ek] + dp[i][j][k]) % mod;
				}
	fl[1][0][0] = 1;
	for (int i = 1; i <= l + 1; i++)
		for (int j = l; j >= 0; j--) // j : 0 k : 1
			for (int k = l; k >= 0; k--) {
				if (!fl[i][j][k]) continue;
				mx[l + 1 - i + j + k][k + ed[i]] = i;
				if ((j + k) >= 2) {
					if (j) fl[i][j - 1][k] = 1;
					if (k) fl[i][j][k - 1] = 1;
					//填上一项 
				}
				if (i != l + 1) {
					//后面选一个
					int um = inp[i] - '0';
					if (j) {
						if (um == 1) fl[i + 1][j - 1][k + 1] = 1;
						if (um == 0) fl[i + 1][j][k] = 1;
						fl[i + 1][j][k] = 1;
					} 
					if (k) {
						if (um == 1) fl[i + 1][j][k] = 1;
						if (um == 0) fl[i + 1][j + 1][k - 1] = 1;
						fl[i + 1][j][k] = 1;
					}
				}
				if (i <= l - 1) {
					int um = inp[i] - '0', vm = inp[i + 1] - '0';
					if (um == 1 || vm == 1) fl[i + 2][j][k + 1] = 1;
					if (um == 0 || vm == 0) fl[i + 2][j + 1][k] = 1;
				}
			}
	ll ans = 0;
	for (int i = 1; i <= l; i++)
		for (int j = 0; j <= i; j++)
			if (mx[i][j]) {
				for (int u = mx[i][j] - 1; u >= 0; u--)
					ans += dp[i][u][j], 
					ans %= mod;	
			}
	cout << ans << endl;
	return 0;
}