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 mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

using namespace std;

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef double ld;

template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

const int maxn = 301;
const i64 P = 998244353;
i64 dp[maxn][maxn][maxn];
int reach[maxn][maxn][maxn];
i64 c[2][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.precision(10);
    cout << fixed;
#ifdef LOCAL_DEFINE
    freopen("input.txt", "rt", stdin);
#endif

    string s;
    cin >> s;
    int n = s.size();
    forn(i, n) forn(z, 2) c[z][i + 1] = c[z][i] + int(s[i] == (char)('0' + z));
    dp[0][0][0] = 1;
    forn(i, n) forn(c0, i + 1) forn(c1, i - c0 + 1) {
        int p = n - i - 1 + c0 + c1;
        forn(z, 2) {
            int nc0 = c0, nc1 = c1;
            if (s[p] - '0' != z) (z ? nc1 : nc0)++;
            (dp[i + 1][nc0][nc1] += dp[i][c0][c1]) %= P;
        }
    }

    forn(i, maxn) forn(j, maxn) forn(k, maxn) reach[i][j][k] = -1e9;
    reach[0][0][0] = 0;
    forn(i, n) forn(c0, i + 1) forn(c1, i - c0 + 1) {
        if (reach[i][c0][c1] < 0) continue;
        int nc0 = c0, nc1 = c1;
        ++(s[i] == '0' ? nc0 : nc1);
        uax(reach[i + 1][c0][c1], reach[i][c0][c1]);
        if (reach[i][c0][c1] > 0) uax(reach[i + 1][nc0][nc1], reach[i][c0][c1] - 1);
        if (i + 2 <= n) {
            uax(reach[i + 2][c0][c1], reach[i][c0][c1] + 1);
            uax(reach[i + 2][nc0][nc1], reach[i][c0][c1]);
            int mc0 = c0, mc1 = c1;
            ++(s[i + 1] == '0' ? mc0 : mc1);
            uax(reach[i + 2][mc0][mc1], reach[i][c0][c1]);
        }
    }

    i64 ans = 0;
    for1(i, n) forn(c0, i + 1) forn(c1, i - c0 + 1) {
        int p = n - i + c0 + c1;
        if (reach[p][c0][c1] >= 0) {
//            cerr << i << ' ' << c0 << ' ' << c1 << ' ' << p << ' ' << dp[i][c0][c1] << '\n';
            (ans += dp[i][c0][c1]) %= P;
        }
    }
    cout << ans << '\n';

#ifdef LOCAL_DEFINE
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
    return 0;
}