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 <algorithm>
#include <cmath>
#include <complex>
#include <cstdio>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define MOD2 1000000007
#define MOD 998244353
#define PRIM 3
#define INF (1 << 29)
#define LINF (1LL << 60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

bool ok[330][330][330]; // pos one two
Int cnt[330][330][330];
Int exact[330][330][330];
string s;

Int ans;

int main()
{
    cin >> s;
    int n = s.size();
    for (int i = 0; i <= n; i++) {
        for (int j = n; j >= 0; j--) {
            for (int k = n; k >= 0; k--) {
                if (i == 0 && j == 0 && k == 0)
                    ok[i][j][k] = true;
                if (i + 1 < n && (s[i] == '0' || s[i + 1] == '0')) {
                    ok[i + 2][j + 1][k] |= ok[i][j][k];
                }
                if (i + 1 < n && (s[i] == '1' || s[i + 1] == '1')) {
                    ok[i + 2][j][k + 1] |= ok[i][j][k];
                }
                if (i < n && s[i] == '0' && k > 0) {
                    ok[i + 1][j + 1][k - 1] |= ok[i][j][k];
                }
                if (i < n && s[i] == '1' && j > 0) {
                    ok[i + 1][j - 1][k + 1] |= ok[i][j][k];
                }
                ok[i + 1][j][k] |= ok[i][j][k];
                if (j)
                    ok[i][j - 1][k] |= ok[i][j][k];

                if (k)
                    ok[i][j][k - 1] |= ok[i][j][k];
            }
        }
    }

    exact[n][0][0] = 1;

    for (int one = 0; one <= n; one++) {
        for (int zero = 0; zero <= n; zero++) {
            int zero_cnt = 0;
            int one_cnt = 0;
            for (int pos = n; pos >= 0; pos--) {
                cnt[pos][one][zero] = 0;
                if (one)
                    cnt[pos][one][zero] +=
                        cnt[pos][one - 1][zero] + exact[pos][one - 1][zero];
                if (zero)
                    cnt[pos][one][zero] +=
                        cnt[pos][one][zero - 1] + exact[pos][one][zero - 1];
                if (pos + 1 <= n) {
                    exact[pos][one][zero] = exact[pos + 1][one][zero];
                    if (s[pos] == '0' && one > 0) {
                        exact[pos][one][zero] += exact[pos][one - 1][zero];
                    }
                    if (s[pos] == '1' && zero > 0) {
                        exact[pos][one][zero] += exact[pos][one][zero - 1];
                    }
                }
                cnt[pos][one][zero] %= MOD;
                exact[pos][one][zero] %= MOD;
            }
            if (one == 0 && zero == 0)
                continue;
            if (ok[n][zero][one]) {
                ans += exact[n][one][zero];
                ans += cnt[n][one][zero];
                ans %= MOD;
                //                cout << zero << " " << one << " " << ans <<
                //                endl;
                continue;
            }

            for (int pos = n - 1; pos >= 0; pos--) {

                if (s[pos] == '0')
                    zero_cnt++;
                else
                    one_cnt++;
                int need_one = one - one_cnt;
                int need_zero = zero - zero_cnt;
                if (need_one < 0 || need_zero < 0)
                    break;
                if (ok[pos][need_zero][need_one]) {
                    ans += exact[pos][need_one][need_zero];
                    ans += cnt[pos][need_one][need_zero];
                    ans %= MOD;
                    //                    cout << pos << " " << need_zero << " "
                    //                    << need_one << " "
                    //                       << ans << endl;

                    break;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}