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>
clock_t t=clock();
namespace my_std{
	using namespace std;
	#define pii pair<int,int>
	#define fir first
	#define sec second
	#define MP make_pair
	#define rep(i,x,y) for (int i=(x);i<=(y);i++)
	#define drep(i,x,y) for (int i=(x);i>=(y);i--)
	#define go(x) for (int i=head[x];i;i=edge[i].nxt)
	#define templ template<typename T>
	#define sz 333
	#define mod 998244353ll
	typedef long long ll;
	typedef double db;
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	templ inline T rnd(T l,T r) {return uniform_int_distribution<T>(l,r)(rng);}
	templ inline bool chkmax(T &x,T y){return x<y?x=y,1:0;}
	templ inline bool chkmin(T &x,T y){return x>y?x=y,1:0;}
	templ inline void read(T& t)
	{
		t=0;char f=0,ch=getchar();double d=0.1;
		while(ch>'9'||ch<'0') f|=(ch=='-'),ch=getchar();
		while(ch<='9'&&ch>='0') t=t*10+ch-48,ch=getchar();
		if(ch=='.'){ch=getchar();while(ch<='9'&&ch>='0') t+=d*(ch^48),d*=0.1,ch=getchar();}
		t=(f?-t:t);
	}
	template<typename T,typename... Args>inline void read(T& t,Args&... args){read(t); read(args...);}
	char __sr[1<<21],__z[20];int __C=-1,__zz=0;
	inline void Ot(){fwrite(__sr,1,__C+1,stdout),__C=-1;}
	inline void print(register int x)
	{
		if(__C>1<<20)Ot();if(x<0)__sr[++__C]='-',x=-x;
		while(__z[++__zz]=x%10+48,x/=10);
		while(__sr[++__C]=__z[__zz],--__zz);__sr[++__C]='\n';
	}
	void file()
	{
		#ifdef NTFOrz
		freopen("a.in","r",stdin);
		#endif
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		cout<<(clock()-t)/1000.0<<'\n';
		#endif
	}
	#ifdef mod
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x%mod) if (y&1) ret=ret*x%mod;return ret;}
	ll inv(ll x){return ksm(x,mod-2);}
	#else
	ll ksm(ll x,int y){ll ret=1;for (;y;y>>=1,x=x*x) if (y&1) ret=ret*x;return ret;}
	#endif
//	inline ll mul(ll a,ll b){ll d=(ll)(a*(double)b/mod+0.5);ll ret=a*b-d*mod;if (ret<0) ret+=mod;return ret;}
}
using namespace my_std;

ll C[sz<<1][sz<<1];

int n;
char s[sz];
bool dp[sz][sz][sz];
int suf[sz];

int main()
{
	file();
	rep(i,0,sz*2-1) C[i][0]=1;
	rep(i,1,sz*2-1) rep(j,1,i) (C[i][j]=C[i-1][j]+C[i-1][j-1])%=mod;
	cin>>(s+1); n=strlen(s+1);
	drep(i,n,1) suf[i]=suf[i+1]+(s[i]=='1');
	dp[0][0][0]=1;
	rep(i,0,n-1) rep(x,0,i) rep(y,0,i-x) if (dp[i][x][y])
	{
		if (x) dp[i+1][x-1+(s[i+1]=='0')][y+(s[i+1]=='1')]=1;
		if (y) dp[i+1][x+(s[i+1]=='0')][y-1+(s[i+1]=='1')]=1;
		dp[i+1][x][y]=1;
		if (i==n-1) continue;
		dp[i+2][x+(s[i+1]=='0')][y+(s[i+1]=='1')]=1;
		dp[i+2][x+(s[i+2]=='0')][y+(s[i+2]=='1')]=1;
	}
	ll ans=0;
	rep(i,1,n) rep(x,0,i) rep(y,0,i-x) if (dp[i][x][y])
	{
		int a=suf[i],b=n-i+1-a;
		(ans+=(a==0?(!x):C[x+a-1][a-1])*(b==0?(!y):C[y+b-1][b-1])%mod)%=mod;
	}
	cout<<ans;
	return 0;
}