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;
//{
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define VAR(v, i) __typeof(i) v=(i)
#define all(v) (v).begin(),(v).end()
#define FORE(i, c) for(VAR(i, (c).begin()); i != (c).end(); ++i)


#define PII pair<int,int>
#define st first
#define nd second
#define pb push_back
#define lint long long int
#define VI vector<int>

#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
};
//{
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

#define make( x) int (x); scanf("%d",&(x));
#define make2( x, y) int (x), (y); scanf("%d%d",&(x),&(y));
#define make3(x, y, z) int (x), (y), (z); scanf("%d%d%d",&(x),&(y),&(z));
#define make4(x, y, z, t) int (x), (y), (z), (t); scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define makev(v,n) VI (v); FOR(i,0,(n)) { make(a); (v).pb(a);} 
#define IOS ios_base::sync_with_stdio(0)
#define HEAP priority_queue

#define read( x) scanf("%d",&(x));
#define read2( x, y) scanf("%d%d",&(x),&(y));
#define read3(x, y, z) scanf("%d%d%d",&(x),&(y),&(z));
#define read4(x, y, z, t) scanf("%d%d%d%d",&(x),&(y),&(z),&(t));
#define readv(v,n) FOR(i,0,(n)) { make(a); (v).pb(a);}
#define jeb() fflush(stdout);
//}

int n;
char s[305];
VI v;
// mag[pos][k] na pozycji pos majac k jedynek ile 
// maksymalnie zer 
int mag[305][305];
int mod = 998244353;

//co[dl][j] dla finalnej dlugosci dl i liczby jedynek j
//maksymalny sufix ktory musi byc 
int co[305][305];
int suf[305];

int dp[305][305][305];

int rob2(int sufix, int zer, int jedynek) {
	if (dp[sufix][zer][jedynek] != -1) return dp[sufix][zer][jedynek];
	int ans = 0;
	if (sufix >= n) {
		if (zer == 0) return 1;
		if (jedynek == 0) return 1;
		ans = rob2(sufix, zer-1, jedynek) + rob2(sufix, zer, jedynek-1);
	} else if (v[sufix] == 0) {
			ans += rob2(sufix+1, zer, jedynek);
			if (jedynek > 0) 
				ans += rob2(sufix, zer, jedynek-1);
	} else if (v[sufix] == 1) {
			ans += rob2(sufix+1, zer, jedynek);
			if (zer > 0) 
				ans += rob2(sufix, zer-1, jedynek);
	}
	ans %= mod;
	dp[sufix][zer][jedynek] = ans;
	return ans;
}

int rob(int sufix, int zer, int jedynek) {
		int wynik = rob2(sufix, zer, jedynek);
		//debug() << imie(sufix) imie(zer) imie(jedynek) imie(wynik);
		return wynik;

}

int main() {
	scanf("%s", s);
	n = strlen(s);
	FOR(i,0,n) v.pb(s[i]-'0');
	suf[n] = 0;
	FORD(i,n-1,0) suf[i] = suf[i+1] + v[i];
	if (n == 1) {
		printf("1\n");
		return 0;
	}
	FOR(i,0,n+1) FOR(j,0,n+1) mag[i][j] = -1e9;
	FOR(i,0,n+1) mag[i][0] = 0;

	FOR(i,2,n+1) {
		// skreslam dwa
		bool jest1 = (v[i-1] == 1 || v[i-2] == 1);
		bool jest0 = (v[i-1] == 0 || v[i-2] == 0);	
		if (jest1) {
			FOR(j,0,n+1) mag[i][j+1] = max(mag[i][j+1], mag[i-2][j]);
		}
		if (jest0) {
			FOR(j,0,n+1) mag[i][j] = max(mag[i][j], mag[i-2][j]+1);
		}
		// skreslam jeden
		jest1 = (v[i-1] == 1);
		jest0 = (v[i-1] == 0);
		FOR(j,0,n+1) mag[i][j] = max(mag[i][j], mag[i-1][j]);
		if (jest1) {
			FOR(j,0,n+1) {
				if (mag[i-1][j] > 0) {
					mag[i][j+1] = max(mag[i][j+1], mag[i-1][j]-1);
				}
			}
		}
		if (jest0) {
			FOR(j,1,n+1) {
				if (mag[i-1][j] >= 0) {
					mag[i][j-1] = max(mag[i][j-1], mag[i-1][j]+1);
				}
			}
		}
	}
	//FOR(i,0,n+1) FOR(j,0,n+1) debug() << imie(i) imie(j) imie(mag[i][j]);
	
	FOR(i,0,n+1) FOR(j,0,n+1) co[i][j] = -1e9;
	FOR(i,0,n+1) {
		FOR(j,0,n+1) {
			if (mag[i][j] < 0) continue;
			FOR(k,0,mag[i][j]+1) {
				int dl = (n-i) + j + k;
				int jed = suf[i] + j;
				co[dl][jed] = max(co[dl][jed], i);
			}
		}
	}
	FOR(i,0,305) FOR(j,0,305) FOR(k,0,305) dp[i][j][k] = -1;
	int ans = 0;
	FOR(i,1,n+1) {
		FOR(j,0,n+1) {
			if (co[i][j] >= 0) {
				int plus_jeden = j-suf[co[i][j]];
				int plus_zero = i-(n-co[i][j])-plus_jeden;
				ans = ans + rob(/*pref=*/co[i][j], plus_zero, plus_jeden);
				if (ans >= mod) ans -= mod;
			}
		}
	}
	printf("%d\n", ans);
}