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>

#define long long long int
using namespace std;

// @author: pashka

int mod = 998244353;

struct mint {
    int value;

    constexpr mint() : value() {}

    mint(const long &x) {
        value = normalize(x);
    }

    static long normalize(const long &x) {
        long v = x % mod;
        if (v < 0) v += mod;
        return v;
    }

    bool operator==(const mint &x) { return value == x.value; };

    mint operator+(const mint &x) { return value + x.value; };

    mint operator*(const mint &x) { return (long) value * x.value; };

    void operator+=(const mint &x) { value = normalize(value + x.value); };
};

bool d[301][301][301];
mint w[301][301][301];

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

    string s;
    cin >> s;
    int n = s.size();
    d[0][0][0] = true;
    for (int i = 0; i < n; i++) {
        for (int j0 = 0; j0 <= n; j0++) {
            for (int j1 = 0; j1 <= n; j1++) {
                if (i < n - 1) {
                    if (s[i] == '0' || s[i + 1] == '0') {
                        d[i + 2][j0 + 1][j1] |= d[i][j0][j1];
                    }
                    if (s[i] == '1' || s[i + 1] == '1') {
                        d[i + 2][j0][j1 + 1] |= d[i][j0][j1];
                    }
                }
                if (j0 > 0) {
                    if (s[i] == '0') {
                        d[i + 1][j0][j1] |= d[i][j0][j1];
                    } else {
                        d[i + 1][j0][j1] |= d[i][j0][j1];
                        d[i + 1][j0 - 1][j1 + 1] |= d[i][j0][j1];
                    }
                }
                if (j1 > 0) {
                    if (s[i] == '0') {
                        d[i + 1][j0][j1] |= d[i][j0][j1];
                        d[i + 1][j0 + 1][j1 - 1] |= d[i][j0][j1];
                    } else {
                        d[i + 1][j0][j1] |= d[i][j0][j1];
                    }
                }
            }
        }
    }
    for (int i = n; i > 0; i--) {
        for (int j0 = 0; j0 <= n; j0++) {
            for (int j1 = 0; j1 <= n; j1++) {
                if(d[i][j0][j1]) {
                    if (s[i - 1] == '0' && j0 > 0) {
                        d[i - 1][j0 - 1][j1] = true;
                    }
                    if (s[i - 1] == '1' && j1 > 0) {
                        d[i - 1][j0][j1 - 1] = true;
                    }
                }
            }
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j0 = 0; j0 <= n; j0++) {
            for (int j1 = 0; j1 <= n; j1++) {
                if(d[i][j0][j1]) {
                    if (s[i] == '0' && d[i + 1][j0 + 1][j1]) {
                        d[i][j0][j1] = false;
                    }
                    if (s[i] == '1' && d[i + 1][j0][j1 + 1]) {
                        d[i][j0][j1] = false;
                    }
                }
            }
        }
    }
    for (int i = 0; i <= n; i++) {
        for (int j0 = n; j0 >= 0; j0--) {
            for (int j1 = n; j1 >= 0; j1--) {
//                if (d[i][j0][j1])
//                    cout << i << " " << j0 << " " << j1 << " " << d[i][j0][j1] << "\n";
                if (d[i][j0][j1]) {
                    w[i][j0][j1] += 1;
                }
                if (i < n) {
                    if (s[i] == '0') {
                        w[i + 1][j0][j1] += w[i][j0][j1];
                        if (j1 > 0) {
                            w[i][j0][j1 - 1] += w[i][j0][j1];
                        }
                    } else {
                        w[i + 1][j0][j1] += w[i][j0][j1];
                        if (j0 > 0) {
                            w[i][j0 - 1][j1] += w[i][j0][j1];
                        }
                    }
                } else {
                    if (j1 > 0) {
                        w[i][j0][j1 - 1] += w[i][j0][j1];
                    }
                    if (j0 > 0) {
                        w[i][j0 - 1][j1] += w[i][j0][j1];
                    }
                }
            }
        }
    }
    mint res = w[n][0][0];
    cout << res.value << "\n";

    return 0;
}