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 int MOD = 998244353;
const int N = 303;


bool state[N][N][N];
int ways[N][N][N];


int main() {
    ios_base::sync_with_stdio(false);

    string s;
    cin >> s;

    int n = s.size();
    state[n][0][0] = true;

    vector <bool> isZero(n), isOne(n);
    for (int i = 0; i < n; i++) {
        isZero[i] = s[i] == '0';
        isOne[i] = !isZero[i];
    }

    for (int suffLen = n; suffLen >= 0; suffLen--) {
        for (int zeros = n; zeros >= 0; zeros--) for (int ones = n; ones >= 0; ones--) {
            if (state[suffLen][zeros][ones]) {
                int p1 = n - suffLen;
                int p2 = p1 + 1;

                if (suffLen >= 2) {
                    for (int p : {p1, p2}) {
                        state[suffLen - 2][zeros + isZero[p]][ones + isOne[p]] = true;
                    }
                }

                if (suffLen >= 1) {
                    if (zeros >= 1) {
                        state[suffLen - 1][zeros][ones] = true;
                        state[suffLen - 1][zeros - 1 + isZero[p1]][ones + isOne[p1]] = true;
                    }

                    if (ones >= 1) {
                        state[suffLen - 1][zeros][ones] = true;
                        state[suffLen - 1][zeros + isZero[p1]][ones - 1 + isOne[p1]] = true;
                    }
                }

                if (zeros >= 2) state[suffLen][zeros - 2][ones] = true;
                if (ones >= 2) state[suffLen][zeros][ones - 2] = true;
                if (zeros >= 1 && ones >= 1) state[suffLen][zeros - 1][ones - 1] = true;
            }
        }
    }

    vector <int> suffZeros(n + 1, 0), suffOnes(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        suffZeros[i] = suffZeros[i - 1] + isZero[n - i];
        suffOnes[i] = suffOnes[i - 1] + isOne[n - i];
    }

    map <pair<int,int>,tuple<int,int,int>> minLenState;

    for (int suffLen = 0; suffLen <= n; suffLen++) {
        for (int zeros = 0; zeros <= n; zeros++) for (int ones = 0; ones <= n; ones++) {
            if (state[suffLen][zeros][ones]) {
                int zerosTotal = zeros + suffZeros[suffLen];
                int onesTotal = ones + suffOnes[suffLen];

                pair <int,int> p = {zerosTotal, onesTotal};

                if (!minLenState.count(p)) {
                    minLenState[p] = tuple <int,int,int> {suffLen, zeros, ones};
                }
            }
        }
    }

    ways[0][0][0] = 1;

    for (int suffLen = 0; suffLen <= n; suffLen++) {
        for (int zeros = 0; zeros <= n; zeros++) for (int ones = 0; ones <= n; ones++) {
            if (suffLen == 0) {
                if (zeros >= 1) {
                    ways[suffLen][zeros][ones] += ways[suffLen][zeros - 1][ones];
                }

                if (ones >= 1) {
                    ways[suffLen][zeros][ones] += ways[suffLen][zeros][ones - 1];
                }

                ways[suffLen][zeros][ones] %= MOD;
            } else {
                int last = isOne[n - suffLen];
                ways[suffLen][zeros][ones] = ways[suffLen-1][zeros][ones];

                if (last == 0) {
                    if (ones >= 1) {
                        ways[suffLen][zeros][ones] = (ways[suffLen][zeros][ones] + ways[suffLen][zeros][ones-1]) % MOD;
                    }
                } else {
                    if (zeros >= 1) {
                        ways[suffLen][zeros][ones] = (ways[suffLen][zeros][ones] + ways[suffLen][zeros-1][ones]) % MOD;
                    }
                }
            }
        }
    }

    int ans = 0;

    for (auto &entry : minLenState) {
        int suffLen, zeros, ones;
        tie(suffLen, zeros, ones) = entry.second;

        if (suffLen + zeros + ones == 0) {
            continue;
        }

        ans = (ans + ways[suffLen][zeros][ones]) % MOD;
    }

    cout << ans;

    return 0;
}