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>
typedef long long int ll;
typedef long double ld;
#define pb push_back
#define pii pair < int , int >
#define F first
#define S second
#define endl '\n'
#define int long long
#define sync ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
#define kill(x) return cout<<x<<'\n', 0;
using namespace std;
const int N=310,mod=998244353;
ll pd[N][N][N];
ll dp[N][N][N];
ll a[N];
ll par[N][2];
int32_t main(){
    string s;
    cin >> s;
    s='*'+s;
    ll n=s.size()-1;
    for (int i=1;i<=n;i++){
        a[i]=s[i]-'0';
        par[i][0]=par[i-1][0];
        par[i][1]=par[i-1][1];
        par[i][a[i]]++;
    }
    dp[n+1][0][0]=1;
    for (int i=0;i<N;i++){
        for (int j=0;j<N;j++){
            if (i==0 && j==0) continue;
            if (i>0)
            dp[n+1][i][j]+=dp[n+1][i-1][j];
            if (j>0)
                dp[n+1][i][j]+=dp[n+1][i][j-1];
            dp[n+1][i][j]%=mod;
        }
    }
    for (int i=n;i;i--){
        for (int j=0;j<N;j++){
            for (int k=0;k<N;k++){
                if (a[i]==1){
                    if (j>0) dp[i][j][k]+=dp[i][j-1][k];
                    if (k>0) dp[i][j][k]+=dp[i+1][j][k-1];
                }
                else{
                    if (j>0) dp[i][j][k]+=dp[i+1][j-1][k];
                    if (k>0) dp[i][j][k]+=dp[i][j][k-1];
                }
                dp[i][j][k]%=mod;
            }
        }
    }
    pd[0][0][0]=1;
    for (int i=2;i<=n;i++){
        for (int j=0;j<N;j++){
            for (int k=0;k<N;k++){
                if (j>0 || k>0) pd[i][j][k]=max(pd[i][j][k],pd[i-1][j][k]);
                if (a[i]==0 && j>0 && k<N-1 && pd[i-1][j-1][k+1]){
                    pd[i][j][k]=1;
                }
                if (a[i]==1 && k>0 && j<N-1 && pd[i-1][j+1][k-1]){
                    pd[i][j][k]=1;
                }
                if (a[i]==0 || a[i-1]==0){
                    if (j>0 && pd[i-2][j-1][k]){
                        pd[i][j][k]=1;
                    }
                }
                if (a[i]==1 || a[i-1]==1){
                    if (k>0 && pd[i-2][j][k-1]){
                        pd[i][j][k]=1;
                    }
                }
            }
        }
    }
    ll ans=0;
    for (int i=2;i<=n;i++){
        for (int j=0;j<N;j++){
            for (int k=0;k<N;k++){
                if (a[i+1]==0 && j<N-1){
                    if (pd[i+1][j+1][k]) pd[i][j][k]=0;
                }
                if (a[i+1]==1 && k<N-1){
                    if (pd[i+1][j][k+1]) pd[i][j][k]=0;
                }
                /*
                if (pd[i][j][k]){
                        cout << i << " " << j << " " << k << endl;
                    ans+=dp[i+1][j][k][0]+dp[i+1][j][k][1]-dp[i+2][j][k][a[i+1]];
                    cout << ans << endl;
                }
                */
                if (pd[i][j][k]){
                //    cout << i << " " << j << " " << k << " " << endl;
                    ans+=dp[i+1][par[n][0]-par[i][0]+j][par[n][1]-par[i][1]+k];
                    ans%=mod;
                //cout << ans << endl;
                }
            }
        }
    }
    cout << ans+1;
}