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 all(x) (x).begin(), (x).end()
#define sz(x) static_cast<int>((x).size())

using LL = long long;
template<class T, size_t D>
struct vec : vector<vec<T, D - 1>> {
  template<class... Args>
  vec(size_t n = 0, Args... args)
    : vector<vec<T, D - 1>>(n, vec<T, D - 1>(args...)) {}
};
template<class T>
struct vec<T, 1> : vector<T> {
  template<class... Args>
  vec(Args... args)
    : vector<T>(args...) {}
};

template<class T>
inline bool asMn(T& a, const T& b) { return a > b ? a = b, true : false; }
template<class T>
inline bool asMx(T& a, const T& b) { return a < b ? a = b, true : false; }
inline int nex(int i, int n) { return i == n - 1 ? 0 : i + 1; }
inline int pre(int i, int n) { return !i ? n - 1 : i - 1; }

mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());

template<int MOD>
struct ModInt {
  int a;
  ModInt(int a_ = 0) {
    a = a_ < MOD ? (a_ < 0 ? a_ + MOD : a_) : a_ - MOD;
  }
  friend ostream& operator<<(ostream& os, const ModInt& o) {
    os << o.a;
    return os;
  }

  ModInt operator+(const ModInt& o) const { return ModInt(a + o.a); }
  ModInt operator-(const ModInt& o) const { return ModInt(a - o.a); }
  ModInt operator*(const ModInt& o) const { return ModInt(static_cast<int>(static_cast<LL>(a) * o.a % MOD)); }
  ModInt operator/(const ModInt& o) const { return *this * o.inv(); }
  ModInt& operator+=(const ModInt& o) { return *this = *this + o; }
  ModInt& operator-=(const ModInt& o) { return *this = *this - o; }
  ModInt& operator*=(const ModInt& o) { return *this = *this * o; }
  ModInt& operator/=(const ModInt& o) { return *this = *this / o; }
  ModInt inv() const { return pow(MOD - 2); }
  template<class T>
  ModInt pow(T exp) const {
    ModInt ret(1), c = *this;
    for (; exp; exp >>= 1, c *= c) {
      if (exp & 1) {
        ret *= c;
      }
    }
    return ret;
  }
};
using Mint = ModInt<998244353>;

int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);

  string s; cin >> s;

  vec<int, 1> n0(sz(s) + 1), n1(sz(s) + 1);
  for (int i = sz(s) - 1; ~i; --i) {
    n0[i] = n0[i + 1] + (s[i] == '0');
    n1[i] = n1[i + 1] + (s[i] == '1');
  }

  vec<bool, 3> f(sz(s) + 1);
  for (int i = 0; i <= sz(s); ++i) {
    f[i] = vec<bool, 2>(n0[0] - n0[i] + 1, n1[0] - n1[i] + 1);
  }
  f[0][0][0] = true;
  for (int i = 0; i < sz(s); ++i) {
    for (int j = sz(f[i]) - 1; ~j; --j) {
      for (int k = sz(f[i][j]) - 1; ~k; --k) {
        if (!f[i][j][k]) {
          continue ;
        }

        if (j + k >= 2) {
          if (j) {
            f[i][j - 1][k] = true;
          }
          if (k) {
            f[i][j][k - 1] = true;
          }
        }
        if (sz(s) - i >= 2) {
          if (s[i] == '0' || s[i + 1] == '0') {
            f[i + 2][j + 1][k] = true;
          }
          if (s[i] == '1' || s[i + 1] == '1') {
            f[i + 2][j][k + 1] = true;
          }
        }
        if (sz(s) - i + j + k >= 2) {
          f[i + 1][j][k] = true;
          if (s[i] == '0') {
            if (k) {
              f[i + 1][j + 1][k - 1] = true;
            }
          } else {
            if (j) {
              f[i + 1][j - 1][k + 1] = true;
            }
          }
        }
      }
    }
  }

  vec<Mint, 3> g(sz(s) + 1, n0[0] + 1, n1[0] + 1);
  g[sz(s)][0][0] = Mint(1);
  for (int i = sz(s); ~i; --i) {
    for (int j = 0; j <= n0[0]; ++j) {
      for (int k = 0; k <= n1[0]; ++k) {
        if (i) {
          if (s[i - 1] == '0' && j < n0[0]) {
            g[i - 1][j + 1][k] += g[i][j][k];
          } else if (s[i - 1] == '1' && k < n1[0]) {
            g[i - 1][j][k + 1] += g[i][j][k];
          }
        }
        if ((i == sz(s) || s[i] == '1') && j < n0[0]) {
          g[i][j + 1][k] += g[i][j][k];
        }
        if ((i == sz(s) || s[i] == '0') && k < n1[0]) {
          g[i][j][k + 1] += g[i][j][k];
        }
      }
    }
  }

  vec<int, 2> mx(n0[0] + 1, n1[0] + 1, -1);
  for (int i = 0; i <= sz(s); ++i) {
    for (int j = 0; j < sz(f[i]); ++j) {
      for (int k = 0; k < sz(f[i][j]); ++k) {
        if (f[i][j][k]) {
          mx[j + n0[i]][k + n1[i]] = i;
        }
      }
    }
  }

  Mint ans;
  for (int i = 0; i <= n0[0]; ++i) {
    for (int j = 0; j <= n1[0]; ++j) {
      if (~mx[i][j]) {
        ans += g[mx[i][j]][i][j];
      }
    }
  }

  cout << ans << '\n';

  return 0;
}