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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#include <time.h>
#include <stack>
#include <array>
#include <list>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll MOD=998244353;
bool ok[303][303][303];
bool ok1[303][303][303];
ll dp[303][303][303];
int main()
{
	string s; cin>>s;
	int n=s.size();
	ok[0][0][0]=1;
	for(int i=0; i<=n; i++){
		for(int j=n; j>=0; j--){
			for(int k=n; k>=0; k--){
				if(!ok[i][j][k]) continue;
				if(j && j+k>=2) ok[i][j-1][k]=1;
				if(k && j+k>=2) ok[i][j][k-1]=1;
				if(i+1<n && (s[i]=='0' || s[i+1]=='0')){
					ok[i+2][j+1][k]=1;
				}
				if(i+1<n && (s[i]=='1' || s[i+1]=='1')){
					ok[i+2][j][k+1]=1;
				}
				if(i<n && j && s[i]=='1'){
					ok[i+1][j-1][k+1]=1;
                  ok[i+1][j][k]=1;
				}
				if(i<n && j && s[i]=='0'){
					ok[i+1][j][k]=1;
				}
				if(i<n && k && s[i]=='0'){
					ok[i+1][j+1][k-1]=1;
                  ok[i+1][j][k]=1;
				}
				if(i<n && k && s[i]=='1'){
					ok[i+1][j][k]=1;
				}
			}
		}
	}
	for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) ok1[i][j][k]=ok[i][j][k];
	for(int i=n; i>=1; i--){
		for(int j=0; j<=n; j++){
			for(int k=0; k<=n; k++){
				if(!ok1[i][j][k]) continue;
				if(s[i-1]=='0' && j) ok1[i-1][j-1][k]=1;
				else if(s[i-1]=='1' && k) ok1[i-1][j][k-1]=1;
			}
		}
	}
	dp[0][0][0]=1;
	for(int i=0; i<=n; i++){
		for(int j=0; i+j<=n; j++){
			for(int k=0; i+j+k<=n; k++){
				(dp[i+1][j][k]+=dp[i][j][k])%=MOD;
				if(i<n && s[n-1-i]=='0'){
					(dp[i][j][k+1]+=dp[i][j][k])%=MOD;
				}else if(i<n){
					(dp[i][j+1][k]+=dp[i][j][k])%=MOD;
				}
			}
		}
	}
	ll ans=0;
	for(int i=0; i<=n; i++){
		for(int j=0; i+j<=n; j++){
			for(int k=0; i+j+k<=n; k++){
				if(i+j+k==0) continue;
				if(ok1[n-i][j][k]) (ans+=dp[i][j][k])%=MOD;
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}