#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 998244353;
bool dp[305][305][305];
ll dp2[305][305][305];
int ma[305][305];

int main(void){
    string s;
    cin >> s;
    int n = s.length();
    VI a(n), sa(n + 1);
    REP(i,n){
        a[i] = s[i] - '0';
        sa[i + 1] = sa[i] + a[i];
    }
    dp[0][0][0] = 1;
    REP(i,n) REP(z,n+1) REP(o,n+1){
        if (!dp[i][z][o]) continue;
        int rz = (i - sa[i]) - z;
        int ro = sa[i] - o;
        if (i + 2 <= n){
            if (a[i] + a[i + 1] == 0) dp[i + 2][z + 1][o] = 1;
            else if (a[i] + a[i + 1] == 1) dp[i + 2][z + 1][o] = dp[i + 2][z][o + 1] = 1;
            else dp[i + 2][z][o + 1] = 1;
        }
        if (rz + (a[i] == 0) > 0 && rz + ro + 1 >= 2) dp[i + 1][z + 1][o] = 1;
        if (ro + (a[i] == 1) > 0 && rz + ro + 1 >= 2) dp[i + 1][z][o + 1] = 1;
        if (rz > 0 && rz + ro >= 2) dp[i][z + 1][o] = 1;
        if (ro > 0 && rz + ro >= 2) dp[i][z][o + 1] = 1;
    }

    VVI ma(n + 1, VI(n + 1, -1));
    REP(i,n+1) REP(j,n+1) REP(k,n+1){
        if (!dp[i][j][k]) continue;
        chmax(ma[j][k], i);
    }

    dp2[0][0][0] = 1;
    REP(i,n) REP(j,n+1) REP(k,n+1){
        // (dp2[i][j + 1][k] += dp2[i][j][k]) %= mod;
        // (dp2[i][j][k + 1] += dp2[i][j][k]) %= mod;
        if (a[n - 1 - i] == 0){
            (dp2[i + 1][j][k] += dp2[i][j][k]) %= mod;
            (dp2[i][j][k + 1] += dp2[i][j][k]) %= mod;
        }else {
            (dp2[i + 1][j][k] += dp2[i][j][k]) %= mod;
            (dp2[i][j + 1][k] += dp2[i][j][k]) %= mod;
        }
    }

    REP(j,n+1) REP(k,n+1) FORR(i,n-1,0){
        if (a[n - 1 - i] == 0) (dp2[i][j + 1][k] += dp2[i + 1][j][k]) %= mod;
        else (dp2[i][j][k + 1] += dp2[i + 1][j][k]) %= mod;
        // (dp2[i][j][k] += dp2[i + 1][j][k]) %= mod;
    }

    // REP(i,n+1){
    //     cout << i << endl;
    //     REP(j,n+1){
    //         REP(k,n+1){
    //             cout << dp2[i][j][k] << " ";
    //         }
    //         cout << endl;
    //     }
    // }

    ll ans = 0;
    REP(i,n+1) REP(j,n+1){
        if (ma[i][j] == -1) continue;
        int x = ma[i][j];
        int o = sa[x] - j, z = (x - sa[x]) - i;
        // cout << x << " " << z << " " << o << " ";
        // cout << dp2[n - x][z][o] << endl;
        (ans += dp2[n - x][z][o]) %= mod;
    }
    cout << ans << endl;


    return 0;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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

### Response

```cpp
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <algorithm>
#include <complex>
#include <array>
#include <functional>
using namespace std;

#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define ALL(c) (c).begin(), (c).end()

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<double> VD;
typedef vector<VI> VVI;
typedef vector<VL> VVL;
typedef vector<VD> VVD;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

template<typename T> void chmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void chmax(T &a, T b) { if (a < b) a = b; }

int in() { int x; scanf("%d", &x); return x; }
ll lin() { ll x; scanf("%lld", &x); return x; }

const ll mod = 998244353;
bool dp[305][305][305];
ll dp2[305][305][305];
int ma[305][305];

int main(void){
    string s;
    cin >> s;
    int n = s.length();
    VI a(n), sa(n + 1);
    REP(i,n){
        a[i] = s[i] - '0';
        sa[i + 1] = sa[i] + a[i];
    }
    dp[0][0][0] = 1;
    REP(i,n) REP(z,n+1) REP(o,n+1){
        if (!dp[i][z][o]) continue;
        int rz = (i - sa[i]) - z;
        int ro = sa[i] - o;
        if (i + 2 <= n){
            if (a[i] + a[i + 1] == 0) dp[i + 2][z + 1][o] = 1;
            else if (a[i] + a[i + 1] == 1) dp[i + 2][z + 1][o] = dp[i + 2][z][o + 1] = 1;
            else dp[i + 2][z][o + 1] = 1;
        }
        if (rz + (a[i] == 0) > 0 && rz + ro + 1 >= 2) dp[i + 1][z + 1][o] = 1;
        if (ro + (a[i] == 1) > 0 && rz + ro + 1 >= 2) dp[i + 1][z][o + 1] = 1;
        if (rz > 0 && rz + ro >= 2) dp[i][z + 1][o] = 1;
        if (ro > 0 && rz + ro >= 2) dp[i][z][o + 1] = 1;
    }

    VVI ma(n + 1, VI(n + 1, -1));
    REP(i,n+1) REP(j,n+1) REP(k,n+1){
        if (!dp[i][j][k]) continue;
        chmax(ma[j][k], i);
    }

    dp2[0][0][0] = 1;
    REP(i,n) REP(j,n+1) REP(k,n+1){
        // (dp2[i][j + 1][k] += dp2[i][j][k]) %= mod;
        // (dp2[i][j][k + 1] += dp2[i][j][k]) %= mod;
        if (a[n - 1 - i] == 0){
            (dp2[i + 1][j][k] += dp2[i][j][k]) %= mod;
            (dp2[i][j][k + 1] += dp2[i][j][k]) %= mod;
        }else {
            (dp2[i + 1][j][k] += dp2[i][j][k]) %= mod;
            (dp2[i][j + 1][k] += dp2[i][j][k]) %= mod;
        }
    }

    REP(j,n+1) REP(k,n+1) FORR(i,n-1,0){
        if (a[n - 1 - i] == 0) (dp2[i][j + 1][k] += dp2[i + 1][j][k]) %= mod;
        else (dp2[i][j][k + 1] += dp2[i + 1][j][k]) %= mod;
        // (dp2[i][j][k] += dp2[i + 1][j][k]) %= mod;
    }

    // REP(i,n+1){
    //     cout << i << endl;
    //     REP(j,n+1){
    //         REP(k,n+1){
    //             cout << dp2[i][j][k] << " ";
    //         }
    //         cout << endl;
    //     }
    // }

    ll ans = 0;
    REP(i,n+1) REP(j,n+1){
        if (ma[i][j] == -1) continue;
        int x = ma[i][j];
        int o = sa[x] - j, z = (x - sa[x]) - i;
        // cout << x << " " << z << " " << o << " ";
        // cout << dp2[n - x][z][o] << endl;
        (ans += dp2[n - x][z][o]) %= mod;
    }
    cout << ans << endl;


    return 0;
}

```