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 <map>
#include <queue>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <functional>
using namespace std;
#pragma warning (disable: 4996)

string S;
long long mod = 998244353;
long long dp[309][309][309];
bool I[309][309][309];

void solve(int pos) {
	// 単純に消す操作
	if (pos >= 1) {
		for (int i = 0; i <= S.size(); i++) {
			for (int j = 0; j <= S.size(); j++) {
				if (I[pos - 1][i][j] == true) I[pos][i][j] = true;
			}
		}
	}

	// 合成させる操作
	if (pos >= 2) {
		for (int i = 0; i <= S.size(); i++) {
			for (int j = 0; j <= S.size(); j++) {
				if (I[pos - 2][i][j] == false) continue;
				int c0 = 0, c1 = 0;
				if (S[pos - 2] == '0') c0++; else c1++;
				if (S[pos - 1] == '0') c0++; else c1++;
				if (c0 >= 1) I[pos][i + 1][j] = true;
				if (c1 >= 1) I[pos][i][j + 1] = true;
			}
		}
	}

	// 前と繋げる操作
	if (pos >= 2) {
		for (int i = 0; i <= S.size(); i++) {
			for (int j = 0; j <= S.size(); j++) {
				if (I[pos - 1][i][j] == false) continue;
				if (i >= 1) {
					int c0 = 1, c1 = 0;
					if (S[pos - 1] == '0') c0++; else c1++;
					if (c0 >= 1) I[pos][i][j] = true;
					if (c1 >= 1) I[pos][i - 1][j + 1] = true;
				}
				if (j >= 1) {
					int c0 = 0, c1 = 1;
					if (S[pos - 1] == '0') c0++; else c1++;
					if (c0 >= 1) I[pos][i + 1][j - 1] = true;
					if (c1 >= 1) I[pos][i][j] = true;
				}
			}
		}
	}
}

int main() {
	cin >> S;

	// DP フェーズ
	dp[0][0][0] = 1;
	for (int i = 0; i < S.size(); i++) {
		for (int j = 0; j < S.size(); j++) {
			for (int k = 0; k < S.size(); k++) {
				if (i + j + k >= S.size()) continue;
				
				if (S[S.size() - 1 - i] == '0') {
					dp[i + 1][j][k] += dp[i][j][k];
					dp[i + 1][j][k] %= mod;
					dp[i][j][k + 1] += dp[i][j][k];
					dp[i][j][k + 1] %= mod;
				}
				else {
					dp[i + 1][j][k] += dp[i][j][k];
					dp[i + 1][j][k] %= mod;
					dp[i][j + 1][k] += dp[i][j][k];
					dp[i][j + 1][k] %= mod;
				}
			}
		}
	}

	// 判定フェーズ
	I[0][0][0] = true;
	for (int i = 1; i <= S.size(); i++) {
		solve(i);
	}
	
	// 答え
	long long Answer = 0;
	for (int i = 0; i <= S.size(); i++) {
		for (int j = 0; j <= S.size(); j++) {
			for (int k = 0; k <= S.size(); k++) {
				bool I1 = I[S.size() - i][j][k];
				if (I1 == true) Answer += dp[i][j][k];
			}
		}
	}
	cout << (Answer + mod - 1) % mod << endl;
	return 0;
}