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 rep(i,a,b) for(int i=a;i<(b);++i)
#define debug(x) cerr<<#x<<": "<<x<<endl
#define trav(a,x) for(auto &a:x)
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    int n = sz(s);
    const ll MOD=998244353;
    vector<vector<vector<ll>>> dp(n+1,vector<vector<ll>>(n+1,vector<ll>(n+1)));
    dp[0][0][0]=1;
    rep(i,0,n+1) rep(j,0,n+1) {
        if(i>0) dp[0][i][j]=dp[0][i-1][j];
        if(j>0) dp[0][i][j]=(dp[0][i][j]+dp[0][i][j-1])%MOD;
    }
    rep(i,1,n+1) {
        dp[i]=dp[i-1];
        if(s[n-i]=='0') {
            rep(j,0,n+1) {
                ll acc = 0;
                rep(k,0,n+1) {
                    dp[i][j][k]=(dp[i][j][k]+acc)%MOD;
                    acc=(acc+dp[i-1][j][k])%MOD;
                }
            }
        }
        else {
            rep(k,0,n+1) {
                ll acc = 0;
                rep(j,0,n+1) {
                    dp[i][j][k]=(dp[i][j][k]+acc)%MOD;
                    acc=(acc+dp[i-1][j][k])%MOD;
                }
            }
        }
    }
    // rep(i,0,n+1) {
    //     rep(j,0,n+1) {
    //         cerr<<dp[n][i][j]<<" ";
    //     }
    //     cerr<<endl;
    // }
    vector<vector<vector<bool>>> pos(n+1,vector<vector<bool>>(n+1,vector<bool>(n+1)));
    pos[0][0][0]=true;
    ll ans = 1;
    rep(i,1,n+1) {
        if(i-1>=0) {
            rep(j,0,n+1) rep(k,0,n+1) if(pos[i-1][j][k]) {
                if(j+k>0) pos[i][j][k] = true;
                if(s[i-1]=='0' && j<n && k>0) pos[i][j+1][k-1]=true;
                if(s[i-1]=='1' && k<n && j>0) pos[i][j-1][k+1]=true;
            }
        }
        if(i-2>=0) {
            rep(j,0,n+1) rep(k,0,n+1) if(pos[i-2][j][k]) {
                if(s[i-2]=='0') pos[i][j+1][k]=true;
                else pos[i][j][k+1]=true;
                
                if(s[i-1]=='0') pos[i][j+1][k]=true;
                else pos[i][j][k+1]=true;
            }
        }
        for(int j=n;j>=0;--j) for(int k=n;k>=0;--k) if(pos[i][j][k] && j+k>=2) {
                    if(j>0) pos[i][j-1][k]=true;
                    if(k>0) pos[i][j][k-1]=true;
                }
    }
    vector<vector<vector<bool>>> mark(n+1,vector<vector<bool>>(n+1,vector<bool>(n+1)));
    for(int i=n;i>0;--i) {
        rep(j,0,n+1) rep(k,0,n+1) if(mark[i][j][k] || pos[i][j][k]) {
            if(s[i-1]=='0' && j>0) mark[i-1][j-1][k] = true;
            if(s[i-1]=='1' && k>0) mark[i-1][j][k-1] = true;
        }
    }
    rep(i,1,n+1) {
        rep(j,0,n+1) rep(k,0,n+1) if(pos[i][j][k] && !mark[i][j][k]) {
            //cerr<<n-i<<" "<<j<<" "<<k<<endl;
            ans=(ans+dp[n-i][j][k])%MOD;
        }
    }
    cout<<ans<<endl;
}