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>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcountll
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC

const int MOD = 998244353;
int mod(int n) {
    n %= MOD;
    if (n < 0) return n + MOD;
    else return n;
}   

const int N = 307;
bool can[N][N][N];
int dp[N][N][N];
//dpijk - number of ways to insert j (0) and k (1) in suffix of length i with largest suffix-subsequence i

void add(int &a, int b) {
    a = mod(a+b);
}   

signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    #define endl '\n'
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    string s;
    cin >> s;
    int n = s.size();
    
    can[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        for (int c0 = i; c0 >= 0; --c0) {
            for (int c1 = i; c1 >= 0; --c1) {
                if (!can[i][c0][c1])
                    continue;

                int t = s[i] - '0';

                can[i+1][c0][c1] = 1;

                if (c0 && c1) {
                    can[i][c0-1][c1] = 1;
                    can[i][c0][c1-1] = 1;
                }   

                if (c0) {
                    can[i+1][c0-1+(t==0)][c1+(t==1)] = 1;
                }   
                if (c1) {
                    can[i+1][c0+(t==0)][c1-1+(t==1)] = 1;
                }   
                if (c0 || c1) {
                    can[i+1][c0][c1] = 1;
                }   

                if (i + 1 < n) {
                    vector <bool> have(2);
                    for (int j = i; j <= i + 1; ++j)
                        have[s[j]-'0'] = 1;
                    if (have[0])
                        can[i+2][c0+1][c1]=1;
                    if (have[1])
                        can[i+2][c0][c1+1]=1;
                }
            }   
        }           
    }   
    
    #ifdef HOME
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                if (can[i][j][k]) {
                    //cout << "can " << i << ' ' << j << ' ' << k << endl;
                }   
            }   
        }   
    }   
    #endif

    dp[0][0][0] = 1;
    for (int i = 0; i < n; ++i) {
        char c = s[n - i - 1];
        for (int j = 0; j <= n; ++j) {
            for (int k = 0; k <= n; ++k) {
                int x = dp[i][j][k];
                if (x == 0)
                    continue;

                add(dp[i+1][j][k], x);
                if (c != '0') {
                    add(dp[i][j+1][k], x);
                }   
                if (c != '1') {
                    add(dp[i][j][k+1], x);
                }
            }   
        }   
    }

    /*
    cout << dp[2][1][0] << endl;
    exit(0);
    */

    int ans = 0;
    for (int p = 0; p <= n; ++p) {
        for (int i = 0; i <= n; ++i)
            for (int j = 0; j <= n; ++j)
                if (can[p][i][j] && dp[n-p][i][j]) {

                    #ifdef HOME
                    //cout << "add " << p << ' ' << i << ' ' << j << " : " << dp[n-p][i][j] << endl;
                    #endif

                    add(ans, dp[n-p][i][j]);
                }
    }   
    cout << mod(ans-1) << endl;
}