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 <cstdio>
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <ctime>
#include <cstring>
#include <cassert>
#include <bitset>
#include <sstream>
#include <queue>

#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define sz(a) ((int) (a).size())
#define eprintf(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long long int64;
typedef long double ldb;

const long double eps = 1e-9;
const int inf = (1 << 30) - 1;
const long long inf64 = ((long long)1 << 62) - 1;
const long double pi = acos(-1);

template <class T> T sqr (T x) {return x * x;}
template <class T> T abs (T x) {return x < 0 ? -x : x;}

const int P = 998244353;

int Sum(int a, int b) {
    return (a + b) % P;
}

int Mult(int a, int b) {
    return (a * (long long) b) % P;
}

int main () {
    ios_base::sync_with_stdio(0);
//  freopen("_input.txt", "rt", stdin);
//  freopen("_output.txt", "wt", stdout);
    
    string s;
    cin >> s;

    int n = sz(s);

    vector<int> cnt_one(n + 1);
    for (int i = 0; i < n; ++i) {
        cnt_one[i + 1] = cnt_one[i] + (s[i] == '1');
    }

    vector<vector<int>> min_sub(n, vector<int>(n + 1, inf));
    min_sub[0][cnt_one[n]] = n;
    
    for (int i = 0; i < n - 1; ++i) {
        for (int cur_one = 0; cur_one <= n - i; ++cur_one) {
            int sub = min_sub[i][cur_one];
            if (sub == inf) {
                continue;
            }

            int cur_zero = n - i - cur_one;
            
            if (sub < 2) {
                if (cur_one > 0) {
                    min_sub[i + 1][cur_one - 1] = 0;
                }
                if (cur_zero > 0) {
                    min_sub[i + 1][cur_one] = 0;
                }
                continue;
            }

            if (s[n - sub] == '1' || s[n - sub + 1] == '1') {
                min_sub[i + 1][cur_one - 1] = min(min_sub[i + 1][cur_one - 1], sub - 2);
            } else if (cur_one > cnt_one[n] - cnt_one[n - sub]) {
                min_sub[i + 1][cur_one - 1] = min(min_sub[i + 1][cur_one - 1], sub - 1);
            }

            if (s[n - sub] == '0' || s[n - sub + 1] == '0') {
                min_sub[i + 1][cur_one] = min(min_sub[i + 1][cur_one], sub - 2);
            } else if (cur_zero > sub - (cnt_one[n] - cnt_one[n - sub])) {
                min_sub[i + 1][cur_one] = min(min_sub[i + 1][cur_one], sub - 1);
            }
        }
    }

    vector<vector<vector<int>>> d(n + 1, vector<vector<int>>(n + 1, vector<int>(n + 1)));

    d[0][0][0] = 1;
    for (int len = 0; len < n; ++len) {
        for (int sub = 0; sub <= len; ++sub) {
            for (int cur_one = 0; cur_one <= len; ++cur_one) {
                for (int cur = 0; cur <= 1; ++cur) {
                    int new_sub = sub + (cur == s[n - sub - 1] - '0');
                    d[len + 1][new_sub][cur_one + cur] = 
                        Sum(d[len + 1][new_sub][cur_one + cur], d[len][sub][cur_one]);
                }
            }
        }
    }

    int res = 0;
    for (int i = 0; i < n; ++i) {
        int cur_res = 0;
        for (int cur_one = 0; cur_one <= n; ++cur_one) {
            if (min_sub[i][cur_one] == inf) {
                continue;
            }

            for (int sub = min_sub[i][cur_one]; sub <= n - i; ++sub) {
                cur_res = Sum(cur_res, d[n - i][sub][cur_one]);
            }
        }
        res = Sum(res, cur_res);
    }
    
    cout << res << "\n";
    return 0;
}