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:
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;

int pd[310][310][310];
int pd2[310][310][310];
int cnt[2][310];
string s;
int n;

int rec(int pos, int av0, int av1) {
    if (av0+av1 == 0) return 1;
    
    int &ret = pd2[pos][av0][av1];
    if (ret == -1) {
        ret = 0;

        if (pos != n && s[pos] == '0') {
            ret = (ret + rec(pos+1, av0, av1)) % mod;
        }
        else if (av0) {
            ret = (ret + rec(pos, av0-1, av1)) % mod;
        }

        if (pos != n && s[pos] == '1') {
            ret = (ret + rec(pos+1, av0, av1)) % mod;
        }
        else if (av1) {
            ret = (ret + rec(pos, av0, av1-1)) % mod;
        }
    }

    // cout << pos << " " << av0 << " " << av1 << " -> " << ret << endl;
    return ret;
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> s;
    n = s.size();

    memset(pd2,-1,sizeof(pd2));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < 2; j++) cnt[j][i+1] = cnt[j][i];
        cnt[s[i]-'0'][i+1]++;
    }

    pd[0][0][0] = 1;
    for (int pos = 0; pos < n; pos++) {
        for (int del0 = 0; del0 <= cnt[0][n]; del0++) {
            for (int del1 = 0; del1 <= cnt[1][n]; del1++) if (pd[pos][del0][del1]) {

                if (pos+2 <= n) {
                    // delete first value
                    int nd0 = del0, nd1 = del1;
                    if (s[pos] == '0') nd0++;
                    if (s[pos] == '1') nd1++;

                    pd[pos+2][nd0][nd1]=1;

                    // delete second value
                    nd0 = del0; nd1 = del1;
                    if (s[pos+1] == '0') nd0++;
                    if (s[pos+1] == '1') nd1++;
                    pd[pos+2][nd0][nd1]=1;
                }

                // delete extras
                int av0 = cnt[0][pos] - del0, av1 = cnt[1][pos] - del1;
                
                if (av0) pd[pos+1][del0+1][del1]=1;
                if (av1) pd[pos+1][del0][del1+1]=1;

                
                // delete values using extras
                int nd0 = del0, nd1 = del1;
                if (s[pos] == '0') nd0++;
                if (s[pos] == '1') nd1++;
                if (av0 || av1) pd[pos+1][nd0][nd1]=1;
            }
        }
    }

    int ans = 0;
    for (int del0 = 0; del0 <= cnt[0][n]; del0++) {
        for (int del1 = 0; del1 <= cnt[1][n]; del1++) {
            // if (del0 != 1 || del1 != 1) continue;
            for (int pos = n; pos >= 0; pos--) if (pd[pos][del0][del1]) {
                // cout << "for del0 = " << del0 << " , del1 = " << del1 << ", pos = " << pos << " ";
                int av0 = cnt[0][pos] - del0, av1 = cnt[1][pos] - del1;
                ans = (ans + rec(pos, av0, av1)) % mod;
                // cout << " -> ret = " << rec(pos,av0,av1) << endl;
                break;
            }
        }
    }

    cout << ans << endl;
}