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 <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
using namespace std;

#ifdef LOCAL
	#define eprintf(...) fprintf(stderr, __VA_ARGS__);fflush(stderr);
#else
	#define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}


const ll MOD = 998244353;
ll add(ll x, ll y) {
	x += y;
	if (x >= MOD) return x - MOD;
	return x;
}
ll sub(ll x, ll y) {
	x -= y;
	if (x < 0) return x + MOD;
	return x;
}
ll mult(ll x, ll y) {
	return (x * y) % MOD;
}
ll bin_pow(ll x, ll p) {
	if (p == 0) return 1;
	if (p & 1) return mult(x, bin_pow(x, p - 1));
	return bin_pow(mult(x, x), p / 2);
}
ll rev(ll x) {
	return bin_pow(x, MOD - 2);
}

const int N = 303;
char s[N];
int n;
bool dp1[N][N][N];
ll dp2[N][N][N];

int main()
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);

	scanf("%s", s);
	n = strlen(s);

	dp1[0][0][0] = 1;
	for (int len = 0; len <= n; len++)
		for (int x = 0; x <= n; x++)
			for (int y = 0; y <= n; y++) {
				if (!dp1[len][x][y]) continue;
				int xx = x, yy = y;
				int nlen = len;
				for (int it = 0; it < 2; it++) {
					if (xx >= 2) dp1[nlen][xx - 1][yy] = 1;
					if (yy >= 2) dp1[nlen][xx][yy - 1] = 1;
					if (xx >= 1 && yy >= 1) {
						dp1[nlen][xx - 1][yy] = 1;
						dp1[nlen][xx][yy - 1] = 1;
					}
					if (nlen == n) break;
					if (s[nlen] == '0')
						xx++;
					else
						yy++;
					nlen++;
				}
				if (xx > x) dp1[nlen][xx - 1][yy] = 1;
				if (yy > y) dp1[nlen][xx][yy - 1] = 1;
			}

	dp2[n][0][0] = 1;
	for (int x = 0; x <= n; x++)
		for (int y = 0; y <= n; y++) {
			for (int p = n; p >= 0; p--) {
				if (dp2[p][x][y] == 0) continue;
				int np = p;
				if (p > 0 && s[p - 1] == '0') np--;
				dp2[np][x + 1][y] = add(dp2[np][x + 1][y], dp2[p][x][y]);
				np = p;
				if (p > 0 && s[p - 1] == '1') np--;
				dp2[np][x][y + 1] = add(dp2[np][x][y + 1], dp2[p][x][y]);
			}
		}

	ll ans = 0;
	for (int x = 0; x <= n; x++)
		for (int y = 0; y <= n; y++) {
			if (x + y == 0) continue;
			if (x + y > n) break;
			int wx = x, wy = y;
			int p = n;
			while(p >= 0) {
				if (dp1[p][wx][wy]) break;
				p--;
				if (p >= 0) {
					if (s[p] == '0')
						wx = max(0, wx - 1);
					else
						wy = max(0, wy - 1);
				}
			}
			for (int i = 0; i <= p; i++)
				ans = add(ans, dp2[i][x][y]);
		}
	printf("%lld\n", ans);

	return 0;
}