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 <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 300;
const int MOD = 998244353;

inline int add(int x, int y) {x += y; return x >= MOD ? x - MOD : x;}
inline int sub(int x, int y) {x -= y; return x < 0 ? x + MOD : x;}
inline int mul(int x, int y) {return (int)(1LL * x * y % MOD);}

int pow_mod(int b, int p) {
	int ret = 1;
	for(int i=p;i;i>>=1,b=mul(b,b))
		if( i & 1 ) ret = mul(ret, b);
	return ret;
}

int comb[2*MAXN + 5][2*MAXN + 5];
int dp[MAXN + 5][MAXN + 5][MAXN + 5];
bool f[MAXN + 5][MAXN + 5][MAXN + 5];
char s[MAXN + 5]; int n;

int main() {
	for(int i=0;i<=2*MAXN;i++) {
		comb[i][0] = 1;
		for(int j=1;j<=i;j++)
			comb[i][j] = add(comb[i-1][j], comb[i-1][j-1]);
	}
	
	scanf("%s", s), n = strlen(s);
	
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			dp[n][i][j] = comb[i + j][i];
	for(int i=n-1;i>=0;i--) {
		for(int j=0;j<=i;j++) {
			for(int k=0;k<=i;k++) {
				dp[i][j][k] = add(dp[i][j][k], dp[i + 1][j][k]);
				if( s[i] == '0' && k ) dp[i][j][k] = add(dp[i][j][k], dp[i][j][k - 1]);
				if( s[i] == '1' && j ) dp[i][j][k] = add(dp[i][j][k], dp[i][j - 1][k]);
			}
		}
	}
	
	f[0][0][0] = true;
	for(int i=0;i<=n;i++) {
		for(int j=i;j>=0;j--) {
			for(int k=i;k>=0;k--) {
				if( j && j + k >= 2 ) f[i][j - 1][k] |= f[i][j][k];
				if( k && j + k >= 2 ) f[i][j][k - 1] |= f[i][j][k];
				
				if( i + 1 <= n ) {
					if( j && s[i] == '1' ) f[i + 1][j - 1][k + 1] |= f[i][j][k];
					if( k && s[i] == '0' ) f[i + 1][j + 1][k - 1] |= f[i][j][k];
					if( j + k ) f[i + 1][j][k] |= f[i][j][k];
				}
				
				if( i + 2 <= n ) {
					if( s[i] == '0' || s[i + 1] == '0' ) f[i + 2][j + 1][k] |= f[i][j][k];
					if( s[i] == '1' || s[i + 1] == '1' ) f[i + 2][j][k + 1] |= f[i][j][k];
				}
			}
		}
	}
	
	int ans = 0;
	for(int i=n;i>=0;i--) {
		for(int j=i;j>=0;j--) {
			for(int k=i;k>=0;k--) {
//				printf("%d %d %d : %d %d\n", i, j, k, f[i][j][k], dp[i][j][k]);
				if( !f[i][j][k] ) continue;
				ans = add(ans, dp[i][j][k]);
				
				int cnt[2] = {};
				for(int l=i-1;l>=0;l--) {
					cnt[s[l] - '0']++;
					if( j < cnt[0] || k < cnt[1] ) break;
					f[l][j - cnt[0]][k - cnt[1]] = false;
				}
			}
		}
	}
	printf("%d\n", ans);
}