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 fi first
#define se second
#define ll long long

const int N = 303;
const int Q = N * 2;
const int mod = 998244353;

using namespace std;

int n;
string s;
int d[N][N][N];
int C[Q][Q];

void add(int &x, int y)
{
        x += y;
        if(x >= mod){
                x -= mod;
        }
}

int A[N], B[N];
bool can[N][N][N];
bool good[N][N];

int solve(int k)
{
        int res = 0;
        int g = min(2 * k, n);
        for(int i = 0; i <= n; i++){
                for(int j = 0; j <= n; j++){
                        good[i][j] = 0;
                }
        }
        for(int i = g - 1; i >= k; i--){
                int need = i + 1 - k;
                for(int x = 0; x <= need; x++){
                        int y = need - x;
                        if(can[i][x][y] && (!good[x + A[g - 1] - A[i]][y + B[g - 1] - B[i]])){
                                good[x + A[g - 1] - A[i]][y + B[g - 1] - B[i]] = 1;
                                add(res, d[i + 1][x][y]);
                        }
                }
        }
        return res;
}

bool get(int i, int j, char need)
{
        if(i >= n || j >= n){
                return false;
        } else if(s[i] == need || s[j] == need){
                return true;
        }
        return false;
}

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

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

        if(n == 1){
                cout << 1 << "\n";
                return 0;
        }

        for(int i = 0; i < n; i++){
                A[i] += (s[i] == '0');
                B[i] += (s[i] == '1');
                A[i + 1] = A[i];
                B[i + 1] = B[i];
        }

        for(int i = 0; i < Q; i++){
                C[i][i] = C[i][0] = 1;
                for(int j = 1; j < i; j++){
                        add(C[i][j], C[i - 1][j]);
                        add(C[i][j], C[i - 1][j - 1]);
                }
        }

        for(int i = 0; i < N; i++){
                for(int j = 0; j < N; j++){
                        d[n][i][j] = C[i + j][i];
                }
        }
        for(int i = n - 1; i >= 0; i--){
                for(int x = 0; x <= n; x++){
                        for(int y = 0; y <= n; y++){
                                if(s[i] == '0'){
                                        add(d[i][x][y], d[i + 1][x][y]);
                                } else if(x > 0){
                                        add(d[i][x][y], d[i][x - 1][y]);
                                }
                                if(s[i] == '1'){
                                        add(d[i][x][y], d[i + 1][x][y]);
                                } else if(y > 0){
                                        add(d[i][x][y], d[i][x][y - 1]);
                                }
                        }
                }
        }

        if(get(0, 1, '0')){
                can[1][1][0] = 1;
        }
        if(get(0, 1, '1')){
                can[1][0][1] = 1;
        }

        for(int i = 2; i < n; i++){
                for(int x = 0; x <= i; x++){
                        for(int y = 0; y <= i; y++){
                                if(get(i, i + 1, '0')){
                                        can[i + 1][x + 1][y] |= can[i - 1][x][y];
                                }
                                if(get(i, i + 1, '1')){
                                        can[i + 1][x][y + 1] |= can[i - 1][x][y];
                                }
                                if(x > 0){
                                        can[i][x][y] |= can[i - 1][x][y];
                                        if(s[i] == '1'){
                                                can[i][x - 1][y + 1] |= can[i - 1][x][y];
                                        }
                                }
                                if(y > 0){
                                        can[i][x][y] |= can[i - 1][x][y];
                                        if(s[i] == '0'){
                                                can[i][x + 1][y - 1] |= can[i - 1][x][y];
                                        }
                                }
                        }
                }
        }

        //cout << solve(2) << "\n";
        //return 0;

        int res = 1;
        for(int k = 1; k < n; k++){
                add(res, solve(k));
                //cout << solve(k) << "\n";
        }

        cout << res << "\n";
}