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:
/*
 * 题目大意：给定 01 串 s，每次可以进行如下操作：
 * 选择前两个字符中的一个删去，将另一个移到 s 的任意位置，
 * 问经过若干次操作后可以得到多少个不同的串。
 * |s| <= 300
 *
 * 算法：
 * 令 f[i][z][o] 表示前 i 位被操作选中过，剩下 z 个 0 和 o 个 1 可不可以达到
 * 令 g[i][z][o] 表示有多少个字符串包含 s[i:n] 为子序列，但是不包含 s[i+1:n] 为子序列，且有 z 个 0 和 o 个 1 的方案数
 */

#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353, maxn = 310;

bool f[maxn][maxn][maxn], h[maxn][maxn][maxn];
int g[maxn][maxn][maxn], cntz[maxn], cnto[maxn];

void upd(int &x, const int &y) {
	x = (x + y < mod ? x + y : x + y - mod);
	return;
}

int main() {
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	int n = s.size(), ans = 0;
	for (int i = n - 1; i >= 0; --i) {
		if(s[i] == '0') cntz[i] = cntz[i + 1] + 1, cnto[i] = cnto[i + 1];
		else cntz[i] = cntz[i + 1], cnto[i] = cnto[i + 1] + 1;
	}
	f[0][0][0] = 1;
	for (int i = 0; i <= n; ++i) for (int z = n - 1; z >= 0; --z) for (int t, o = n - 1; o >= 0; --o) if(t = f[i][z][o]) {
		if(z >= 2) f[i][z - 1][o] = 1;
		if(o >= 2) f[i][z][o - 1] = 1;
		if(z >= 1 && o >= 1) f[i][z - 1][o] = f[i][z][o - 1] = 1;
		if(i < n) {
			if(s[i] == '0') {
				if(z >= 1) f[i + 1][z][o] = 1;
				if(o >= 1) f[i + 1][z + 1][o - 1] = f[i + 1][z][o] = 1;
				if(i + 1 < n) {
					if(s[i + 1] == '0') f[i + 2][z + 1][o] = 1;
					else f[i + 2][z + 1][o] = f[i + 2][z][o + 1] = 1;
				}
			}
			else {
				if(o >= 1) f[i + 1][z][o] = 1;
				if(z >= 1) f[i + 1][z - 1][o + 1] = f[i + 1][z][o] = 1;
				if(i + 1 < n) {
					if(s[i + 1] == '1') f[i + 2][z][o + 1] = 1;
					else f[i + 2][z + 1][o] = f[i + 2][z][o + 1] = 1;
				}
			}
		}
	}
	g[n][0][0] = 1;
	for (int i = n; i > 0; --i) for (int z = 0; z <= n; ++z) for (int t, o = 0; o + z <= n; ++o) if(t = g[i][z][o]) {
		if(s[i - 1] == '0') upd(g[i - 1][z + 1][o], t), upd(g[i][z][o + 1], t);
		else upd(g[i - 1][z][o + 1], t), upd(g[i][z + 1][o], t);
	}
	for (int i = n; i >= 0; --i) for (int z = 0; z <= n; ++z) for (int o = 0; o + z <= n; ++o) {
		h[i][z][o] = h[i + 1][z][o] | (z >= cntz[i] && o >= cnto[i] && f[i][z - cntz[i]][o - cnto[i]]);
		if(h[i][z][o]) upd(ans, g[i][z][o]);
	}
	cout << ans << endl;
	return 0;
}