#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
const ll mod = 998244353;
//ll dp[155][155][305];
ll ans = 0;
ll checker[305][305][305];
ll dp[305][305][305];
set<string> st;
void dfs(string S) {
    if(st.find(S) != st.end()) return;
  cerr << S << endl;
    st.insert(S);
    if(S.size() < 2) return;
    string T = S.substr(2, S.size());
    string Add = S.substr(0, 2);
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j <= T.size(); j++) {
        string to = T;
        to.insert(to.begin() + j, Add[i]);
        dfs(to);
      }
    }
}

int main() {
    string S;
  cin >> S;
  if(S.size() <= 3) {
    dfs(S);
    cout << st.size() << endl;
    return 0;
  }
    checker[0][0][0] = 1;
    for(int k = 0; k <= S.size(); k++) {
        for(int i = S.size(); i >= 0; i--) {
            for(int j = S.size(); j >= 0; j--) {
                if(!checker[i][j][k]) continue;
                //cerr << i << " " << j << " " << k << endl;
                if(k + 2 <= S.size()) {
                    string T = S.substr(k, 2);
                    if(T != "11") checker[i+1][j][k+2] = 1;
                    if(T != "00") checker[i][j+1][k+2] = 1;
                }
                if(i >= 2) checker[i-2][j][k] = 1;
                if(j >= 2) checker[i][j-2][k] = 1;
                if(i >= 1 and j >= 1) checker[i-1][j-1][k] = 1;
                if(i >= 1 or j >= 1) checker[i][j][k+1] = 1;
                if(i >= 1 and k + 1 <= S.size() and S[k] == '1') {
                    checker[i-1][j+1][k+1] = 1;
                }
                if(j >= 1 and k + 1 <= S.size() and S[k] == '0') {
                    checker[i+1][j-1][k+1] = 1;
                }
            }
        }
    }
    for(int k = S.size(); k >= 0; k--) {
        for(int i = 0; i <= S.size(); i++) {
            for(int j = 0; j <= S.size(); j++) {
                if(checker[i][j][k] == 0) continue;
                if(checker[i][j][k] == 1) {
                    //cerr << i + j + (S.size() - k) << " " << i << " " << j << " " << k << endl;
                }
                if(k == 0) continue;
                ll newi = i;
                ll newj = j;
                if(S[k-1] == '0') newi--;
                if(S[k-1] == '1') newj--;
                if(newi < 0 or newj < 0) continue;
                //checker[newi][newj][k+1] = 2;
                checker[newi][newj][k-1] = 2;
            }
        }
    }
    dp[0][0][S.size()] = 1;
    for(int k = S.size(); k >= 0; k--) {
        for(int i = 0; i <= S.size(); i++) {
            for(int j = 0; j <= S.size(); j++) {
                if(k < S.size()) {
                    dp[i][j][k] += dp[i][j][k+1];
                    if(S[k] == '0' and j > 0) dp[i][j][k] += dp[i][j-1][k];
                    if(S[k] == '1' and i > 0) dp[i][j][k] += dp[i-1][j][k];
                } else {
                    if(j > 0) dp[i][j][k] += dp[i][j-1][k];
                    if(i > 0) dp[i][j][k] += dp[i-1][j][k];
                }
                dp[i][j][k] %= mod;
                if(checker[i][j][k] == 1 and dp[i][j][k]) {
                    //cerr << i << " " << j << " " << k << " " << S.substr(k, S.size()) << " " << dp[i][j][k] << endl;
                    ans += dp[i][j][k];
                    ans %= mod;
                }
            }
        }
    }
    //cerr << dp[1][0][6] << " " << checker[1][0][6] << endl;
    //cerr << dp[0][1][6] << " " << checker[0][1][6] << endl;
    ans += mod - 1;
    ans %= mod;
    cout << ans << endl;
    return 0;
}

### Prompt

Please formulate a CPP solution to the following 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

### Response

```cpp
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1e18;
const ll mod = 998244353;
//ll dp[155][155][305];
ll ans = 0;
ll checker[305][305][305];
ll dp[305][305][305];
set<string> st;
void dfs(string S) {
    if(st.find(S) != st.end()) return;
  cerr << S << endl;
    st.insert(S);
    if(S.size() < 2) return;
    string T = S.substr(2, S.size());
    string Add = S.substr(0, 2);
    for(int i = 0; i < 2; i++) {
      for(int j = 0; j <= T.size(); j++) {
        string to = T;
        to.insert(to.begin() + j, Add[i]);
        dfs(to);
      }
    }
}

int main() {
    string S;
  cin >> S;
  if(S.size() <= 3) {
    dfs(S);
    cout << st.size() << endl;
    return 0;
  }
    checker[0][0][0] = 1;
    for(int k = 0; k <= S.size(); k++) {
        for(int i = S.size(); i >= 0; i--) {
            for(int j = S.size(); j >= 0; j--) {
                if(!checker[i][j][k]) continue;
                //cerr << i << " " << j << " " << k << endl;
                if(k + 2 <= S.size()) {
                    string T = S.substr(k, 2);
                    if(T != "11") checker[i+1][j][k+2] = 1;
                    if(T != "00") checker[i][j+1][k+2] = 1;
                }
                if(i >= 2) checker[i-2][j][k] = 1;
                if(j >= 2) checker[i][j-2][k] = 1;
                if(i >= 1 and j >= 1) checker[i-1][j-1][k] = 1;
                if(i >= 1 or j >= 1) checker[i][j][k+1] = 1;
                if(i >= 1 and k + 1 <= S.size() and S[k] == '1') {
                    checker[i-1][j+1][k+1] = 1;
                }
                if(j >= 1 and k + 1 <= S.size() and S[k] == '0') {
                    checker[i+1][j-1][k+1] = 1;
                }
            }
        }
    }
    for(int k = S.size(); k >= 0; k--) {
        for(int i = 0; i <= S.size(); i++) {
            for(int j = 0; j <= S.size(); j++) {
                if(checker[i][j][k] == 0) continue;
                if(checker[i][j][k] == 1) {
                    //cerr << i + j + (S.size() - k) << " " << i << " " << j << " " << k << endl;
                }
                if(k == 0) continue;
                ll newi = i;
                ll newj = j;
                if(S[k-1] == '0') newi--;
                if(S[k-1] == '1') newj--;
                if(newi < 0 or newj < 0) continue;
                //checker[newi][newj][k+1] = 2;
                checker[newi][newj][k-1] = 2;
            }
        }
    }
    dp[0][0][S.size()] = 1;
    for(int k = S.size(); k >= 0; k--) {
        for(int i = 0; i <= S.size(); i++) {
            for(int j = 0; j <= S.size(); j++) {
                if(k < S.size()) {
                    dp[i][j][k] += dp[i][j][k+1];
                    if(S[k] == '0' and j > 0) dp[i][j][k] += dp[i][j-1][k];
                    if(S[k] == '1' and i > 0) dp[i][j][k] += dp[i-1][j][k];
                } else {
                    if(j > 0) dp[i][j][k] += dp[i][j-1][k];
                    if(i > 0) dp[i][j][k] += dp[i-1][j][k];
                }
                dp[i][j][k] %= mod;
                if(checker[i][j][k] == 1 and dp[i][j][k]) {
                    //cerr << i << " " << j << " " << k << " " << S.substr(k, S.size()) << " " << dp[i][j][k] << endl;
                    ans += dp[i][j][k];
                    ans %= mod;
                }
            }
        }
    }
    //cerr << dp[1][0][6] << " " << checker[1][0][6] << endl;
    //cerr << dp[0][1][6] << " " << checker[0][1][6] << endl;
    ans += mod - 1;
    ans %= mod;
    cout << ans << endl;
    return 0;
}

```