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>

namespace IO
{
char gc()
{
#ifdef FREAD
	static char buf[1<<21], *P1 = buf, *P2 = buf;
	if(P1 == P2)
	{
		P1 = buf;
		P2 = buf + fread(buf, 1, 1<<21, stdin);
		if(P1 == P2) return EOF;
	}
	return *(P1++);
#else
	return getchar();
#endif
}
template<typename Tp> bool get1(Tp &x)
{
	bool neg = 0;
	char c = gc();
	while( c != EOF && (c < '0' || c > '9') && c != '-' ) c = gc();
	if(c == '-') c = gc(), neg = 1;
	if(c == EOF) return false;
	x = 0;
	for(; c>='0' && c<='9'; c = gc()) x = x*10 + c - '0';
	if(neg) x = -x;
	return true;
}
template<typename Tp> void printendl(Tp x)
{
	if(x<0)putchar('-'),x=-x;
	static short a[40], sz;
	sz = 0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
	puts("");
}
} // namespace IO
using IO::get1;
using IO::printendl;
#define get2(x,y) get1(x) && get1(y)
#define get3(x,y,z) get2(x,y) && get1(z)
#define get4(x,y,z,w) get3(x,y,z) && get1(w)
#define pb push_back
#define mp std::make_pair
#define ff first
#define ss second
typedef long long LL;
typedef unsigned long long uLL;
typedef std::pair<int,int> pii;
const int inf = 0x3f3f3f3f;
const LL Linf = 1ll<<61;

const int maxn = 311;
const int mod = 998244353;
inline void add(int &x, int y) { x += y; if(x >= mod) x -= mod; }

char s[maxn];
int n, dp[maxn][maxn][maxn];
bool can[maxn][maxn][maxn];

int main()
{
	scanf("%s", s);
	n = strlen(s);
	
	can[0][0][0] = 1;
	for(int k=0; k<n; k++)
	{
		for(int i=0; i<=n; i++) for(int k0=0; k0<=n; k0++)
		{
			int k1 = i - k - k0;
			if(k1 < 0) continue;
			if(!can[i][k0][k1]) continue;
			if(k0 && k0 + k1 >= 2) can[i][k0-1][k1] = 1;
			if(k1 && k0 + k1 >= 2) can[i][k0][k1-1] = 1;
			if(i < n)
			{
				if(k0 || k1) can[i+1][k0][k1] = 1;
				int p = s[i] - '0';
				if(p == 0 && k1) can[i+1][k0+1][k1-1] = 1;
				if(p == 1 && k0) can[i+1][k0-1][k1+1] = 1;
				if(i < n - 1)
				{
					int q = s[i+1] - '0';
					if(p == 0 || q == 0) can[i+2][k0+1][k1] = 1;
					if(p == 1 || q == 1) can[i+2][k0][k1+1] = 1;
				}
			}
		}
	}
	
	dp[0][0][0] = 1;
	for(int i=0; i<=n; i++) for(int n0=0; n0<=n; n0++) for(int n1=0; n1<=n; n1++) if(dp[i][n0][n1])
	{
		int pos = s[n - 1 - (i - n0 - n1)] - '0';
		
		add(dp[i+1][n0][n1], dp[i][n0][n1]);
		if(pos == 0) add(dp[i+1][n0][n1+1], dp[i][n0][n1]);
		else add(dp[i+1][n0+1][n1], dp[i][n0][n1]);
	}
	
	for(int i=n-1; i>=0; i--) for(int k0=0; k0<=n; k0++) for(int k1=0; k1<=n; k1++)
	{
		if(can[i+1][k0][k1])
		{
			int p = s[i] - '0';
			if(p == 0 && k0) can[i][k0-1][k1] = 1;
			if(p == 1 && k1) can[i][k0][k1-1] = 1;
		}
	}
	
	int ans = 0;
	for(int i=1; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) if(dp[i][j][k])
	{
		int pos = n - (i - j - k);
		if(can[pos][j][k]) add(ans, dp[i][j][k]);
	}
	printendl(ans);
	return 0;
}