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 <bits/stdc++.h>
using namespace std;


void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

void pre(){


}

void solve(){


}
const ll mod = 998244353;
bool p[309][309][309];
ll f[309][309];
ll dp[2][309][309];
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	string s;cin>>s;
	p[0][0][0]=1;
	int n = sz(s);
	repA(i,1,n){
		rep(j,301) rep(k,301) p[i][j][k] = p[i-1][j][k];
		if(s[i-1]=='0'){
			rep(k,301) repA(j,1,300) p[i][j][k]|=p[i-1][j-1][k+1];
		}
		if(s[i-1]=='1'){
			rep(j,301) repA(k,1,300) p[i][j][k]|=p[i-1][j+1][k-1];
		}
		if(i>=2&&(s[i-2]=='0'||s[i-1]=='0')){
			rep(j,301) rep(k,301) p[i][j+1][k]|=p[i-2][j][k];
		}
		if(i>=2&&(s[i-2]=='1'||s[i-1]=='1')){
			rep(j,301) rep(k,301) p[i][j][k+1]|=p[i-2][j][k];
		}
	}
	int cnt0=0,cnt1=0;
	ll fns = 0;
	int cur = 0;
	dp[0][0][0]=1;
	rep(j,301) rep(k,301) {
		if(j) dp[0][j][k]+=dp[0][j-1][k];
		if(k) dp[0][j][k]+=dp[0][j][k-1];
		dp[0][j][k]%=mod;
	}
	repD(i,n,0){
		repA(j,cnt0,300) repA(k,cnt1,300) if(!f[j][k]&&p[i][j-cnt0][k-cnt1]){
			f[j][k]=1;
			fns+=dp[cur][j][k];
		}
		if(i){
			if(s[i-1]=='1'){
				rep(j,301) dp[1-cur][j][0] = 0;
				repA(k,1,300) dp[1-cur][0][k] = dp[cur][0][k-1];
				repA(j,1,300) repA(k,1,300) dp[1-cur][j][k]=(dp[1-cur][j-1][k]+dp[cur][j][k-1])%mod;
				cnt1++;
			}
			else{
				rep(j,301) dp[1-cur][0][j] = 0;
				repA(k,1,300) dp[1-cur][k][0] = dp[cur][k-1][0];
				repA(j,1,300) repA(k,1,300) dp[1-cur][j][k]=(dp[cur][j-1][k]+dp[1-cur][j][k-1])%mod;
				cnt0++;	
			}
			cur=1-cur;
		}
	}
	cout<<(fns+mod-1)%mod;
	return 0;
}