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;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#define x first
#define y second
#define mp make_pair
#define pb push_back
template <typename TYPE> inline void chkmax(TYPE &x,TYPE y){x<y?x=y:0;}
template <typename TYPE> inline void chkmin(TYPE &x,TYPE y){y<x?x=y:0;}
template <typename TYPE> void readint(TYPE &x)
{
    x=0;int f=1;char c;
    for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1;
    for(;isdigit(c);c=getchar())x=x*10+c-'0';
    x*=f;
}
const int MAXN=305,MOD=998244353;
inline int dmy(int x){return x>=MOD?x-MOD:x;}
inline void inc(int &x,int y){x=dmy(x+y);}

int n;
char s[MAXN];
int f[MAXN][MAXN][MAXN],cnt[2];
bool g[MAXN][MAXN][MAXN];

int main()
{
	#ifdef LOCAL
	freopen("code.in","r",stdin);
//	freopen("code.out","w",stdout);
	#endif
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i)++cnt[s[i]-'0'];
	for(int j=0;j<=cnt[1];++j)f[n+1][0][j]=1;
	for(int i=1;i<=cnt[0];++i)
	{
		f[n+1][i][0]=1;
		for(int j=1;j<=cnt[1];++j)
			f[n+1][i][j]=dmy(f[n+1][i-1][j]+f[n+1][i][j-1]);
	}
	for(int k=n;k;--k)
		for(int i=0;i<=cnt[0];++i)
			for(int j=0;j<=cnt[1];++j)
			{
				if(i)inc(f[k][i][j],f[k+(s[k]=='0')][i-1][j]);
				if(j)inc(f[k][i][j],f[k+(s[k]=='1')][i][j-1]);
			}
	cnt[0]=cnt[1]=0;
	g[0][0][0]=1;
	for(int k=0;k<n;++k)
	{
		for(int i=0;i<=cnt[0];++i)
			for(int j=0;j<=cnt[1];++j)
			{
				if(!g[k][i][j])continue;
				if(s[k+1]=='0')
				{
					g[k+1][i+1][j]=1;
					if(j<cnt[1])g[k+1][i][j+1]=1;
					g[k+2][i+1][j]=1;
				}
				else
				{
					g[k+1][i][j+1]=1;
					if(i<cnt[0])g[k+1][i+1][j]=1;
					g[k+2][i][j+1]=1;
				}
				if(s[k+2]=='0')g[k+2][i+1][j]=1;
				else g[k+2][i][j+1]=1;
			}
		++cnt[s[k+1]-'0'];
	}
	int ans=0;
	for(int i=0;i<=cnt[0];++i)
		for(int j=0;j<=cnt[1];++j)
		{
			int pos=-1;
			for(int k=n;k>=0;--k)if(g[k][i][j]){pos=k;break;}
//cerr<<i<<" "<<j<<" "<<pos<<" : "<<f[pos+1][cnt[0]-i][cnt[1]-j]<<endl;
			if(pos<0)continue;
			inc(ans,f[pos+1][cnt[0]-i][cnt[1]-j]);
		}
	printf("%d\n",dmy(ans+MOD-1));
	return 0;
}