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 pb push_back
#define pll pair <ll, ll>
#define mp make_pair
#define pyshnapyshnakaa ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define x first
#define y second
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define plll pair <pair <ll, ll>, ll>
#define pllll pair <pair <ll, ll>, pair <ll, ll> >
#define psl pair <string, ll>
#define all(a) a.begin(), a.end()
#define vvl vector <vector <ll> >
 
typedef long long ll;

typedef long double ld;
 
using namespace std;
 
const ll maxn = 4e2;
const ll mod = 998244353;

ll n, m, k, t;

bool dp[maxn][maxn][maxn];

ll dp1[maxn][maxn][maxn];

ll cnt0[maxn];

ll cnt1[maxn];

ll ans = 0;

string s;

void count_dp() {
    dp[0][0][0] = 1;
    ll q, w, e;
    for (q = 0; q <= n; q++) {
        for (w = n; w >= 0; w--) { /// cnt of 0s
            for (e = n; e >= 0; e--) { /// cnt of 1s
                if (!dp[q][w][e]) {
                    continue;
                }
                dp[q + 1][w][e] = 1;
                // both from string
                if (q + 2 <= n) {
                    if (s[q] == '0' || s[q + 1] == '0') {
                        dp[q + 2][w + 1][e] = 1;
                    }
                    if (s[q] == '1' || s[q + 1] == '1') {
                        dp[q + 2][w][e + 1] = 1;
                    }
                }
                // both from pocket
                if (w + e >= 2 && w >= 1) {
                    dp[q][w - 1][e] = 1;
                }
                if (w + e >= 2 && e >= 1) {
                    dp[q][w][e - 1] = 1;
                }
                // one from string, one from pocket, erase from pocket
                if (q + 1 <= n) {
                    if (s[q] == '0') {
                        if (e >= 1) {
                            dp[q + 1][w + 1][e - 1] = 1;
                        }
                        if (w >= 1) {
                            dp[q + 1][w][e] = 1;
                        }
                    }
                    if (s[q] == '1') {
                        if (e >= 1) {
                            dp[q + 1][w][e] = 1;
                        }
                        if (w >= 1) {
                            dp[q + 1][w - 1][e + 1] = 1;
                        }
                    }
                    // one from string, one from pocket, erase from string
                    if (w + e >= 1) {
                        dp[q + 1][w][e] = 1;
                    }
                }
            }
        }
    }
}

void count_dp1() {
    reverse(all(s));
    ll q, w, e;
    for (q = 1; q <= n; q++) {
        cnt0[q] = cnt0[q - 1] + (s[q - 1] == '0');
        cnt1[q] = cnt1[q - 1] + (s[q - 1] == '1');   
    }
    dp1[0][0][0] = 1;
    for (q = 0; q < n; q++) {
        for (w = 0; w <= n; w++) {
            for (e = 0; e <= n; e++) {
                dp1[q][w + (s[q] == '1')][e + (s[q] == '0')] += dp1[q][w][e];
                dp1[q][w + (s[q] == '1')][e + (s[q] == '0')] %= mod;
                dp1[q + 1][w][e] += dp1[q][w][e];
                dp1[q + 1][w][e] %= mod;
                // assert(cnt0[q] >= 0 && cnt1[q] >= 0);
                // if (q == 2 && w == 2 && e == 0)cout << "DP1 DEBUG " << q << " " << w << " " << e << " " << dp1[q][w][e] << endl;
                // if (q != 0) {
                //     if (s[q - 1] == '0') {
                //         // cout << "KUU " << q << " " << w << " " << e << endl;
                //         // if (dp1[q][w][e] !=)
                //         // cout << dp1[q - 1][w + 1][e] << endl; 
                //         dp1[q - 1][w + 1][e] -= dp1[q][w][e];
                //         dp1[q - 1][w + 1][e] += mod;
                //         dp1[q - 1][w + 1][e] %= mod;
                //     }
                //     else {
                //         dp1[q - 1][w][e + 1] -= dp1[q][w][e];
                //         dp1[q - 1][w][e + 1] += mod;
                //         dp1[q - 1][w][e + 1] %= mod;
                //     }
                //     // dp1[q][w][e] = (dp1[q][w][e] + mod) % mod;
                //     // dp1[q][w][e] -= (dp1[q - 1][w][e]);
                // }
            }
        }
    }
}

void merge() {
    ll q, w, e;
    for (q = 0; q <= n; q++) {
        for (w = 0; w <= n; w++) {
            for (e = 0; e <= n; e++) {
                if (dp[q][w][e]) {
                    // cout << n - q << " " << w << " " << e << " " << dp1[n - q][w][e] << endl;
                    ans += dp1[n - q][w][e];
                    ans %= mod;
                }
            }
            // cout << endl;
        }
        // cout << endl;
    }
}

int main() {
    pyshnapyshnakaa;
    ll q, w, e, a, b, c;
    cin >> s;
    n = s.length();
    count_dp();
    count_dp1();
    merge();
    cout << (ans - 1 + mod) % mod;
    return 0;
}