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;

#ifdef NeverBeRed
#include "debug.h"
#else
#define debug(...) 9715
#endif
typedef long long ll;
typedef long double ld;
typedef complex<ld> point;
#define F first
#define S second

const int mod = 998244353;
int dp[305][305][305];

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

int main()
{
	#ifdef TurnRed
		//freopen("a.in", "r", stdin);
		//freopen("a.out", "w", stdout);
	#endif

	ios_base::sync_with_stdio(0), cin.tie(0);

	string s;
	cin >> s;

	int n = s.length();
	dp[0][0][0] = true;
	for (int p = 0; p < n; ++p)
		for (int z = 0; z <= n; ++z)
			for (int o = 0; o <= n; ++o)
				if (dp[p][z][o])
				{
					if (z >= 2) dp[p][z-2][o] = true;
					if (o >= 2) dp[p][z][o-2] = true;
					if (z && o) dp[p][z-1][o-1] = true;
					if (z || o) dp[p+1][z][o] = true;
					if (z && s[p] == '1') dp[p+1][z-1][o+1] = true;
					if (o && s[p] == '0') dp[p+1][z+1][o-1] = true;
					if (p+1 < n)
					{
						if (s[p] == '0' || s[p+1] == '0') dp[p+2][z+1][o] = true;
						if (s[p] == '1' || s[p+1] == '1') dp[p+2][z][o+1] = true;
					}
				}

	vector<vector<int>> f(2, vector<int>(n+1));
	for (int i = n-1; i >= 0; --i)
	{
		++f[s[i]-'0'][i];
		f[0][i] += f[0][i+1];
		f[1][i] += f[1][i+1];
	}

	vector<vector<int>> cnt(n+1, vector<int>(n+1, -1));
	for (int p = 0; p <= n; ++p)
		for (int z = 0; z <= n; ++z)
			for (int o = 0; o <= n; ++o)
				if (dp[p][z][o])
				{
//					debug(p, z, o);
					int nz = z + f[0][p];
					int no = o + f[1][p];
					cnt[nz][no] = max(cnt[nz][no], p);
				}

//	for (auto i : cnt)
//		debug(i);

	memset(dp, 0, sizeof dp);
	for (int z = 0; z <= n; ++z)
		for (int o = 0; o <= n; ++o)
			if (cnt[z][o] != -1)
			{
				int p = cnt[z][o];
				dp[p][z - f[0][p]][o - f[1][p]] = 1;
			}

	for (int p = 0; p <= n; ++p)
		for (int z = n; z >= 0; --z)
			for (int o = n; o >= 0; --o)
			{
				if (p < n && s[p] == '0')
					add(dp[p+1][z][o], dp[p][z][o]);
				else if (z)
					add(dp[p][z-1][o], dp[p][z][o]);

				if (p < n && s[p] == '1')
					add(dp[p+1][z][o], dp[p][z][o]);
				else if (o)
					add(dp[p][z][o-1], dp[p][z][o]);
			}

	cout << dp[n][0][0] << "\n";

	return 0;
}