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>
#define RI register int
#define CI const int&
using namespace std;
const int N=305,mod=998244353;
char s[N]; int n,f[N][N][N],ans; bool vis[N][N][N]; // f[i][j][k]: length i; j 0s to add; k 1s to add
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
int main()
{
	RI i,j,k; scanf("%s",s+1); n=strlen(s+1); s[0]='2';
	for (f[0][0][0]=1,i=0;i<n;++i) for (j=0;j<=i;++j)
	for (k=0;j+k<=i;++k) if (f[i][j][k])
	{
		int c=s[n-(i-j-k)]-'0'; inc(f[i+1][j][k],f[i][j][k]);
		if (c) inc(f[i+1][j+1][k],f[i][j][k]); else inc(f[i+1][j][k+1],f[i][j][k]);
	}
	for (vis[0][0][0]=vis[n][0][0]=1,i=n-1;i;--i)
	for (j=0;j<=i;++j) for (k=0;j+k<=i;++k)
	{
		int c1=s[n-(i-j-k)]-'0',c2=s[n-(i-j-k)-1]-'0',t[3]; t[2]=0;
		if (t[0]=j,t[1]=k,++t[0],t[c1])
		{
			if (--t[c1],t[c2]&&(c1==0||c2==0)) --t[c2];
		}
		vis[i][j][k]|=vis[i+1][t[0]][t[1]];
		if (t[0]=j,t[1]=k,++t[1],t[c1])
		{
			if (--t[c1],t[c2]&&(c1==1||c2==1)) --t[c2];
		}
		vis[i][j][k]|=vis[i+1][t[0]][t[1]];
	}
	for (i=1;i<=n;++i) for (j=0;j<=i;++j) for (k=0;j+k<=i;++k)
	if (vis[i][j][k]) inc(ans,f[i][j][k]); return printf("%d",ans),0;
}