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;

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int main(){
    string str;
    cin >> str;
    int N = str.size();
    vector<int> S(N);
    for(int i=0; i<N; i++) S[i] = str[i] - '0';

    static int64_t dp[310][310][310];
    dp[N][0][0] = 1;
    for(int i=N; i>0; i--) for(int j=0; j<N; j++) for(int k=0; k<N; k++){
        int64_t v = dp[i][j][k];
        if(S[i-1]){
            add(dp[i][j+1][k], v);
            add(dp[i-1][j][k], v);
        }else{
            add(dp[i][j][k+1], v);
            add(dp[i-1][j][k], v);
        }
    }

    static bool can[310][310][310];
    can[0][0][0] = true;

    int64_t ans = 0;
    for(int i=0; i<=N; i++) for(int j=0; j<N; j++) for(int k=0; k<N; k++) if(can[i][j][k]){
        //cerr<<i<<j<<k<<" "<<dp[i][j][k]<<endl;
        add(ans, dp[i][j][k]);
        can[i+1][j][k] = true;
        if(i<N-1){
            if(S[i] || S[i+1]) can[i+2][j][k+1] = true;
            if(!S[i] || !S[i+1]) can[i+2][j+1][k] = true;
        }
        if(i<N && j && S[i]) can[i+1][j-1][k+1] = true;
        if(i<N && k && !S[i]) can[i+1][j+1][k-1] = true;
    }
    add(ans, MOD-1);

    cout << ans << endl;
    return 0;
}