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 <iostream>
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
const int mod=998244353;
const int maxn=300+5;
int n; char S[maxn];
int mx[maxn][maxn];
int f[maxn][maxn][maxn];
int C[maxn][maxn];
int sx[maxn],sy[maxn];
bool g[maxn][maxn][maxn];
inline int add(int x) {return x>=mod?x-mod:x;}
void init() {
	for(int i=0;i<=n;++i) {
		C[i][0]=C[i][i]=1;
		for(int j=1;j<i;++j) C[i][j]=add(C[i-1][j-1]+C[i-1][j]);
	}
}
int main() {
	scanf("%s",S+1),n=strlen(S+1);
	init();
	f[n+1][0][0]=1;
	for(int i=n;i>=1;--i) {
		for(int a=0;a<=n;++a) for(int b=0;b<=n;++b) {
			f[i][a][b]=f[i+1][a][b];
			if(S[i]=='0'&&b) f[i][a][b]=add(f[i][a][b]+f[i][a][b-1]);
			if(S[i]=='1'&&a) f[i][a][b]=add(f[i][a][b]+f[i][a-1][b]);
		}
	}
	g[0][0][0]=1;
	for(int i=0;i<=n;++i) {
		for(int a=n;a>=0;--a) for(int b=n;b>=0;--b) if(g[i][a][b]) {
			if(a+b>=2) {
				if(a) g[i][a-1][b]=1;
				if(b) g[i][a][b-1]=1;
			}
			if(i+2<=n) {
				if(S[i+1]=='0'||S[i+2]=='0') g[i+2][a+1][b]=1;
				if(S[i+1]=='1'||S[i+2]=='1') g[i+2][a][b+1]=1;
			}
			if(i+1<=n&&(a||b)) {
				g[i+1][a][b]=1;
				if(S[i+1]=='0'&&b) g[i+1][a+1][b-1]=1;
				if(S[i+1]=='1'&&a) g[i+1][a-1][b+1]=1; 
			}
		}
	}
	memset(mx,-1,sizeof(mx));
	for(int i=n;i>=0;--i) {
		for(int a=0;a<=n;++a) for(int b=0;b<=n;++b) if(g[i][a][b]) {
			if(mx[a+sx[i]][b+sy[i]]==-1) mx[a+sx[i]][b+sy[i]]=i;
		}
		sx[i-1]=sx[i],sy[i-1]=sy[i];
		if(S[i]=='0') ++sx[i-1]; else ++sy[i-1];
	}
	int an=0;
	for(int x=0;x<=n;++x) for(int y=0;y<=n;++y) if(mx[x][y]!=-1) {
		int t=mx[x][y]+1,xx=x-sx[t-1],yy=y-sy[t-1];
		int r=an;
		for(int a=0;a<=xx;++a) for(int b=0;b<=yy;++b) if(f[t][a][b]) {
			an=(an+(ll)f[t][a][b]*C[xx+yy-a-b][xx-a])%mod;
		}
//		debug("%d %d %d %d\n",xx,yy,t-1,an-r);
	}
	printf("%d\n",an);
	return 0;
}