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;
const int maxn=319,mod=998244353;
inline void Add(int &a,int b){a=a+b>=mod?a+b-mod:a+b;}
char s[maxn];int n,f[maxn][maxn][maxn],g[maxn][maxn][maxn];
int main()
{
	scanf("%s",s+1);n=strlen(s+1);reverse(s+1,s+n+1);
	g[0][0][0]=1;s[n+1]='2';
	for(int i=0;i<n;i++) for(int j=0;j<=i;j++) for(int k=0;j+k<=i;k++) if(g[i][j][k])
	{
		int v=s[i-j-k+1]-'0';
		Add(g[i+1][j][k],g[i][j][k]);
		if(v) Add(g[i+1][j+1][k],g[i][j][k]);
		else Add(g[i+1][j][k+1],g[i][j][k]);
	}
	f[n][0][0]=1;
	for(int i=n-1;i;i--) for(int j=0;j<=i;j++) for(int k=0;j+k<=i;k++)
	{
		int va=s[i-j-k+1]-'0',vb=s[i-j-k+2]-'0',nxt[3];
		nxt[0]=j+1;nxt[1]=k;nxt[2]=0;
		if(nxt[va]){nxt[va]--;if(nxt[vb]&&(va==0||vb==0))nxt[vb]--;}
		f[i][j][k]|=f[i+1][nxt[0]][nxt[1]];
		nxt[0]=j;nxt[1]=k+1;nxt[2]=0;
		if(nxt[va]){nxt[va]--;if(nxt[vb]&&(va==1||vb==1))nxt[vb]--;}
		f[i][j][k]|=f[i+1][nxt[0]][nxt[1]];
	}
	int ans=0;
	for(int i=1;i<=n;i++) for(int j=0;j<=i;j++) for(int k=0;j+k<=i;k++)
		if(f[i][j][k]) Add(ans,g[i][j][k]);
	cout<<ans<<endl;
	return 0;
}