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;
 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define FILL(a, value) memset(a, value, sizeof(a))
 
#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
 
typedef long long LL;
typedef pair<int, int> PII;

const int mod = 998244353;
const int MAX = 304;

int add(int a, int b)
{
	return a + b < mod ? a + b : a + b - mod;
}

int sub(int a, int b)
{
	return a - b >= 0 ? a - b : a - b + mod;
}

int mult(int a, int b)
{
	return (LL)a * b % mod;
}

void updAdd(int& x, int val)
{
	x += val;
	if(x >= mod)
		x -= mod;
}

bool f[MAX][MAX][MAX];
int g[MAX][MAX][MAX];

int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	string s;
	cin >> s;
	f[0][0][0] = true;
	FOR(i, 0, SZ(s))
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
				if(f[i][c0][c1])
				{
					assert(2 * (c0 + c1) <= i);
					f[i + 1][c0][c1] = true;
					if(c0)
						f[i + 1][c0 - 1 + (s[i] == '0')][c1 + (s[i] == '1')] = true;
					if(c1)
						f[i + 1][c0 + (s[i] == '0')][c1 - 1 + (s[i] == '1')] = true;
					if(i + 1 < SZ(s))
					{
						f[i + 2][c0 + (s[i] == '0')][c1 + (s[i] == '1')] = true;
						f[i + 2][c0 + (s[i + 1] == '0')][c1 + (s[i + 1] == '1')] = true;
					}
				}
	g[SZ(s)][0][0] = 1;
	RFOR(i, SZ(s) + 1, 1)
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
			{
				updAdd(g[i - 1][c0][c1], g[i][c0][c1]);
				updAdd(g[i][c0 + (s[i - 1] == '1')][c1 + (s[i - 1] == '0')], g[i][c0][c1]);
			}
	int ans = mod - 1;
	FOR(i, 0, SZ(s) + 1)
		FOR(c0, 0, SZ(s) + 1)
			FOR(c1, 0, SZ(s) + 1)
				if(f[i][c0][c1])
				{
					//cerr << i << " " << c0 << " " << c1 << " " << g[i][c0][c1] << endl;
					updAdd(ans, g[i][c0][c1]);
				}
	cout << ans << "\n";
	return 0;
}