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 <cmath>
#include <ctime>
#include <cstdlib>
#include <cassert>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <string>
#include <algorithm>
#include <utility>
#define llint long long
#define inf 1e18
#define rep(x, s, t) for(llint (x) = (s); (x) < (t); (x)++)
#define Rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define mod 998244353

using namespace std;
typedef pair<llint, llint> P;

llint n;
string s;
bool dp[305][305][305];
llint dp2[305][305][305];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	llint n = s.size();
	s = "#" + s;
	
	dp[0][0][0] = true;
	for(int i = 0; i < n; i++){
		for(int j = n; j >= 0; j--){
			for(int k = n; k >= 0; k--){
				if(!dp[i][j][k]) continue;
				
				if(i+2 <= n) dp[i+1][j][k] = true;
				
				if(i+2 <= n && s[i+2] == '0' && j+1 <= n) dp[i+2][j+1][k] = true;
				if(i+2 <= n && s[i+2] == '1' && k+1 <= n) dp[i+2][j][k+1] = true;
				
				if(i+2 <= n && s[i+1] == '0' && j+1 <= n) dp[i+2][j+1][k] = true;
				if(i+2 <= n && s[i+1] == '1' && k+1 <= n) dp[i+2][j][k+1] = true;
				
				if(i+1 <= n && s[i+1] == '0' && j >= 1) dp[i+1][j+1-1][k] = true;
				if(i+1 <= n && s[i+1] == '0' && j+1 <= n && k >= 1) dp[i+1][j+1][k-1] = true;
				if(i+1 <= n && s[i+1] == '1' && k >= 1) dp[i+1][j][k+1-1] = true;
				if(i+1 <= n && s[i+1] == '1' && k+1 <= n && j >= 1) dp[i+1][j-1][k+1] = true;
				
				if(i+1 <= n && (j >= 1 || k >= 1)) dp[i+1][j][k] = true;
				
				if(i+1 <= n && j >= 2) dp[i][j-2][k] = true;
				if(i+1 <= n && k >= 2) dp[i][j][k-2] = true;
				if(i+1 <= n && j >= 1 && k >= 1) dp[i][j-1][k-1] = true;
				
				if(i+1 <= n && j >= 1) dp[i][j-1][k] = true;
				if(i+1 <= n && k >= 1) dp[i][j][k-1] = true;
			}
		}
	}
	
	/*for(int i = 0; i <= n; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				cout << dp[i][j][k] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}*/
	
	dp2[n+1][0][0] = 1;
	for(int i = n+1; i > 1; i--){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				if(s[i-1] == '0') (dp2[i-1][j][k] += dp2[i][j][k]) %= mod;
				else if(j+1 <= n) (dp2[i][j+1][k] += dp2[i][j][k]) %= mod;
				
				if(s[i-1] == '1') (dp2[i-1][j][k] += dp2[i][j][k]) %= mod;
				else if(k+1 <= n) (dp2[i][j][k+1] += dp2[i][j][k]) %= mod;
			}
		}
	}
	
	/*for(int i = n+1; i >= 1; i--){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				cout << dp2[i][j][k] << " ";
			}
			cout << endl;
		}
		cout << endl;
	}*/
	
	llint ans = 0;
	for(int i = 1; i <= n+1; i++){
		for(int j = 0; j <= n; j++){
			for(int k = 0; k <= n; k++){
				if(dp[i-1][j][k]) ans += dp2[i][j][k], ans %= mod;
			}
		}
	}
	cout << ans << endl;
	
	return 0;
}