#include <bits/stdc++.h>

using namespace std;

const int MAXN = 5.1e5;

template<int MOD>
struct Modular {
  int value;
  Modular(const Modular& k) : value(k.value) {}
 
  template<typename V>
  Modular(const V& v) : value(v % MOD) {
    if (value < 0) {
      value += MOD;
    }
  }
  
  Modular() : Modular(0) {}
 
  Modular& operator+=(Modular const& b) { value += b.value; if (value >= MOD) value -= MOD; return *this; } 
  Modular& operator-=(Modular const& b) { value -= b.value; if (value < 0) value += MOD; return *this; }
  Modular& operator*=(Modular const& b) { value = (long long)value * b.value % MOD; return *this; }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { return *this += 1; }
  Modular operator--(int) { return *this -= 1; }

  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }
  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) { return os << a.value; }
  friend bool operator==(Modular const& a, Modular const& b) { return a.value == b.value; }
  friend bool operator!=(Modular const& a, Modular const& b) { return a.value != b.value; }
};
 
template <int T, typename V>
Modular<T> mexp(Modular<T> a, V e) {
  if (a == 0) return e == 0 ? 1 : 0; 
  Modular<T> res = 1; 
  while (e) { 
    if (e & 1) 
      res *= a; 
    a *= a; 
    e >>= 1; 
  }
  return res;
}

using Mint = Modular<998244353>;

const int N = 310;

Mint C[N][N][N][2];
int S[N][N][N];

void Run() {
  string t;
  cin >> t;
  const int n = t.size();
  S[0][0][0] = 1;
  for (int pref = 1; pref <= n; ++pref) {
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (j > 0 && pref >= 2 && (t[pref - 1] == '1' || t[pref - 2] == '1'))
          S[pref][i][j] |= S[pref - 2][i][j - 1];
        if (i > 0 && pref >= 2 && (t[pref - 1] == '0' || t[pref - 2] == '0'))
          S[pref][i][j] |= S[pref - 2][i - 1][j];
        if (i + j > 0)
          S[pref][i][j] |= S[pref - 1][i][j];
        if (j && t[pref - 1] == '1')
          S[pref][i][j] |= S[pref - 1][i + 1][j - 1];
        if (i && t[pref - 1] == '0')
          S[pref][i][j] |= S[pref - 1][i - 1][j + 1];
      }
    }
  }
  C[n][0][0][0] = C[n][0][0][1] = 1;
  int none = n, nzero = n;
  for (int i = n; i >= 0; --i) {
    if (i < n && t[i] == '1') none = i;
    if (i < n && t[i] == '0') nzero = i;
    for (int j = 0; j <= n; ++j) {
      for (int k = 0; k <= n; ++k) {
        if (j) C[i][j][k][0] += C[i][j - 1][k][0];
        if (j && t[i - 1] != '0') C[i][j][k][1] += C[i][j - 1][k][1];
        if (k) C[i][j][k][0] += C[i][j][k - 1][0];
        if (k && t[i - 1] != '1') C[i][j][k][1] += C[i][j][k - 1][1];
        for (int ty = 0; ty < 2; ++ty) {
          C[i][j][k][ty] += C[i + 1][j][k][1];
        }
      }
    }
  }
  Mint ans = 0;
  vector<vector<bool> > banned(2 * n + 1, vector<bool>(2 * n + 1));
  int freq[2] = {0, 0};
  for (int suff = n; suff >= 0; --suff) {
    if (suff < n) ++freq[t[suff] - '0'];
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (!banned[i + freq[0]][j + freq[1]] && S[suff][i][j]) {
          ans += C[suff][i][j][0];
          banned[i + freq[0]][j + freq[1]] = true;
        }
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Run();
  return 0;
}

### Prompt

Create a solution in CPP for 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>

using namespace std;

const int MAXN = 5.1e5;

template<int MOD>
struct Modular {
  int value;
  Modular(const Modular& k) : value(k.value) {}
 
  template<typename V>
  Modular(const V& v) : value(v % MOD) {
    if (value < 0) {
      value += MOD;
    }
  }
  
  Modular() : Modular(0) {}
 
  Modular& operator+=(Modular const& b) { value += b.value; if (value >= MOD) value -= MOD; return *this; } 
  Modular& operator-=(Modular const& b) { value -= b.value; if (value < 0) value += MOD; return *this; }
  Modular& operator*=(Modular const& b) { value = (long long)value * b.value % MOD; return *this; }
  Modular& operator++() { return *this += 1; }
  Modular& operator--() { return *this -= 1; }
  Modular operator++(int) { return *this += 1; }
  Modular operator--(int) { return *this -= 1; }

  friend Modular inverse(Modular a) { return mexp(a, MOD - 2); }
  Modular& operator/=(Modular const& b) { return *this *= inverse(b); }
  friend Modular operator+(Modular a, Modular const b) { return a += b; }
  friend Modular operator-(Modular a, Modular const b) { return a -= b; }
  friend Modular operator-(Modular const a) { return 0 - a; }
  friend Modular operator*(Modular a, Modular const b) { return a *= b; }
  friend Modular operator/(Modular a, Modular const b) { return a /= b; }
  friend std::ostream& operator<<(std::ostream& os, Modular const& a) { return os << a.value; }
  friend bool operator==(Modular const& a, Modular const& b) { return a.value == b.value; }
  friend bool operator!=(Modular const& a, Modular const& b) { return a.value != b.value; }
};
 
template <int T, typename V>
Modular<T> mexp(Modular<T> a, V e) {
  if (a == 0) return e == 0 ? 1 : 0; 
  Modular<T> res = 1; 
  while (e) { 
    if (e & 1) 
      res *= a; 
    a *= a; 
    e >>= 1; 
  }
  return res;
}

using Mint = Modular<998244353>;

const int N = 310;

Mint C[N][N][N][2];
int S[N][N][N];

void Run() {
  string t;
  cin >> t;
  const int n = t.size();
  S[0][0][0] = 1;
  for (int pref = 1; pref <= n; ++pref) {
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (j > 0 && pref >= 2 && (t[pref - 1] == '1' || t[pref - 2] == '1'))
          S[pref][i][j] |= S[pref - 2][i][j - 1];
        if (i > 0 && pref >= 2 && (t[pref - 1] == '0' || t[pref - 2] == '0'))
          S[pref][i][j] |= S[pref - 2][i - 1][j];
        if (i + j > 0)
          S[pref][i][j] |= S[pref - 1][i][j];
        if (j && t[pref - 1] == '1')
          S[pref][i][j] |= S[pref - 1][i + 1][j - 1];
        if (i && t[pref - 1] == '0')
          S[pref][i][j] |= S[pref - 1][i - 1][j + 1];
      }
    }
  }
  C[n][0][0][0] = C[n][0][0][1] = 1;
  int none = n, nzero = n;
  for (int i = n; i >= 0; --i) {
    if (i < n && t[i] == '1') none = i;
    if (i < n && t[i] == '0') nzero = i;
    for (int j = 0; j <= n; ++j) {
      for (int k = 0; k <= n; ++k) {
        if (j) C[i][j][k][0] += C[i][j - 1][k][0];
        if (j && t[i - 1] != '0') C[i][j][k][1] += C[i][j - 1][k][1];
        if (k) C[i][j][k][0] += C[i][j][k - 1][0];
        if (k && t[i - 1] != '1') C[i][j][k][1] += C[i][j][k - 1][1];
        for (int ty = 0; ty < 2; ++ty) {
          C[i][j][k][ty] += C[i + 1][j][k][1];
        }
      }
    }
  }
  Mint ans = 0;
  vector<vector<bool> > banned(2 * n + 1, vector<bool>(2 * n + 1));
  int freq[2] = {0, 0};
  for (int suff = n; suff >= 0; --suff) {
    if (suff < n) ++freq[t[suff] - '0'];
    for (int i = 0; i <= n; ++i) {
      for (int j = 0; j <= n; ++j) {
        if (!banned[i + freq[0]][j + freq[1]] && S[suff][i][j]) {
          ans += C[suff][i][j][0];
          banned[i + freq[0]][j + freq[1]] = true;
        }
      }
    }
  }
  cout << ans << '\n';
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  Run();
  return 0;
}

```