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 <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <algorithm>
#define MOD 998244353
#define forn(a, n) for(int a = 0; a<(int) (n); ++a)
#define dforn(a, n) for(int a = (n)-1; a>=0; --a)
#define forall(a, all) for(__typeof(all.begin()) a = all.begin(); a != all.end(); ++a)
#define EPS 0.000000000001
using namespace std;
typedef long long tint;
typedef pair<tint, tint> pii;
typedef vector<tint> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<vvvi> vvvvi;

int gcd(int a, int b) {
	return b ? gcd(b, a%b) : a;
}

void dfs(int voy, int ceros, int unos, string s, vvvi &reach) {
	//cout << voy << " " << ceros << " " << unos << endl;
	if(reach[voy][ceros][unos]) {
		return;
	}
	reach[voy][ceros][unos] = 1;
	
	int n = s.size();
	if(n - voy >= 2) {
		if(s[voy] == '0' || s[voy+1] == '0') {
			dfs(voy+2, ceros+1, unos, s, reach);
		}
		if(s[voy] == '1' || s[voy+1] == '1') {
			dfs(voy+2, ceros, unos+1, s, reach);
		}
	}
	
	if(n - voy >= 1) {
		if(ceros) dfs(voy, ceros-1, unos, s, reach);
		if(unos) dfs(voy, ceros, unos-1, s, reach);
		if(ceros && s[voy] == '1') dfs(voy+1, ceros-1, unos+1, s, reach);
		if(unos && s[voy] == '0') dfs(voy+1, ceros+1, unos-1, s, reach);
		if(ceros || unos || n-voy >= 2) dfs(voy+1, ceros, unos, s, reach);
	}
	
	if(ceros+unos >=2) {
		if(ceros) dfs(voy, ceros-1, unos, s, reach);
		if(unos) dfs(voy, ceros, unos-1, s, reach);
	}
}

tint solvedp(int voy, int ceros, int unos, string s, vvvi &dp) {
	int n = s.size();
	if(voy == n+1) {
		return ceros == 0 && unos == 0;
	}
	
	if(dp[voy][ceros][unos] != -1) {
		return dp[voy][ceros][unos];
	}
	
	tint ans = 0;
	if(s[voy-1] == '1' && ceros) {
		ans += solvedp(voy, ceros-1, unos, s, dp);
	}
	if(s[voy-1] == '0' && unos) {
		ans += solvedp(voy, ceros, unos-1, s, dp);
	}
	ans += solvedp(voy+1, ceros, unos, s, dp);
	ans %= MOD;
	dp[voy][ceros][unos] = ans;
	return ans;
}

int main()
{
	string s;
	cin >> s;
	tint n = s.size();
	
	vvvi reach(n+1, vvi(n, vi(n, 0)));
	vvvi dp(n+1, vvi(n, vi(n, -1)));
	dfs(0, 0, 0, s, reach);
	
	tint ans = 0;
	forn(i, n+1) forn(j, n) forn(k, n) {
		if(reach[i][j][k]) {
			//cout << i << " " << j << " " << k << " " << solvedp(i, j, k, s, dp) << " " << endl;
			ans += solvedp(i, j, k, s, dp);
			ans %= MOD;
		}
	}
	cout << ans << endl;
}