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;

using LL = long long;

template<typename T>
ostream& operator << (ostream& out, const vector<T>& v) {
    out << "[";
    for(auto& x : v) {
        out << x << ", ";
    }
    return out << "]";
}

template<typename S, typename T>
ostream& operator << (ostream& out, const pair<S, T>& p) {
    return out << "{" << p.first << ", " << p.second << "}";
}

bool reachable[310][310][310];

int N;
vector<int> V;
int suff_ones[310];
int suff_zeroes[310];
int shortest_suff[310][310];

void explore(int n, int z, int o) {
    if(z < 0 or o < 0) {
        return;
    }
    if(reachable[n][z][o]) {
        return;
    }
    reachable[n][z][o] = 1;
    shortest_suff[z + suff_zeroes[n]][o + suff_ones[n]] = max(shortest_suff[z + suff_zeroes[n]][o + suff_ones[n]], n);
    if(z + o >= 2) {
        explore(n, z - 1, o); //delete from pool
        explore(n, z, o - 1); //delete from pool
    }
    if(n == N) {
        return;
    }
    if(V[n] == 0) {
        explore(n + 1, z + 1, o - 1); //delete from pool and add from vector
    } else {
        explore(n + 1, z - 1, o + 1); //delete from pool and add from vector
    }
    if(z + o + (N - n) >= 2) {
        explore(n + 1, z, o);
    }
    if(n + 2 <= N) {
        if(V[n] == 0 or V[n + 1] == 0) {
            explore(n + 2, z + 1, o); //delete and add from vector
        }
        if(V[n] == 1 or V[n + 1] == 1) {
            explore(n + 2, z, o + 1); //delete and add from vector
        }
    }
}

const LL MOD = 998244353;
LL dp[310][310][310];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    string S;
    cin >> S;
    for(char c : S) {
        if(c == '0') {
            V.push_back(0);
        } else {
            V.push_back(1);
        }
    }
    N = S.length();
    for(int n = N - 1; n >= 0; --n) {
        suff_ones[n] = suff_ones[n + 1] + V[n];
        suff_zeroes[n] = suff_zeroes[n + 1] + 1 - V[n];
    }
    memset(shortest_suff, -1, sizeof(shortest_suff));
    explore(0, 0, 0);
    
    for(int n = N; n >= 0; --n) {
        for(int z = 0; z <= N; ++z) {
            for(int o = 0; o <= N; ++o) {
                if(n == N) {
                    if(z == 0 or o == 0) {
                        dp[N][z][o] = 1;
                    } else {
                        dp[N][z][o] = (dp[N][z - 1][o] + dp[N][z][o - 1]) % MOD;
                    }
                    continue;
                }
                if(V[n] == 0) {
                    dp[n][z][o] = (((z > 0) ? (dp[n + 1][z - 1][o]) : (0)) + ((o > 0) ? (dp[n][z][o - 1]) : (0))) % MOD;
                } else {
                    dp[n][z][o] = (((z > 0) ? (dp[n][z - 1][o]) : (0)) + ((o > 0) ? (dp[n + 1][z][o - 1]) : (0))) % MOD;
                }
            }
        }
    }
    
    LL ans = 0;
    for(int z = 0; z <= N; ++z) {
        for(int o = 0; o <= N; ++o) {
            if(shortest_suff[z][o] >= 0) {
                ans = (ans + dp[shortest_suff[z][o]][z][o]) % MOD;
            }
        }
    }
    cout << ans << "\n";
    
    
    return 0;
}