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 <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

#define TRACE(x) std::cout << #x << " = " << x << "\n"
#define _ << " _ " <<

using namespace std;

template <int32_t P>
struct ModInt_t {
  constexpr static auto mod = P;

  int32_t value;

  static_assert(P < (1 << 30) - 1, "2xP must fit into 32-bit signed integer");

  ModInt_t() : value{0} {};

  constexpr explicit ModInt_t(int32_t v) : value(v) {
    if (value >= P || value <= -P) value %= P;
    if (value < 0) value += P;
  };

  constexpr explicit ModInt_t(int64_t v) {
    v %= P;
    if (v < 0) v += P;
    value = v;
  };

  explicit operator bool() const { return value != 0; }
  explicit operator int32_t() const { return value; }

  ModInt_t& operator+=(const ModInt_t& other) {
    value += other.value;
    if (value >= P) value -= P;
    return *this;
  }

  ModInt_t& operator-=(const ModInt_t& other) {
    value -= other.value;
    if (value < 0) value += P;
    return *this;
  }

  ModInt_t& operator*=(const ModInt_t& other) {
    int64_t result = static_cast<int64_t>(value) * other.value;
    value = static_cast<int32_t>(result % P);
    return *this;
  }

  static ModInt_t inverse(ModInt_t x) { return ModInt_t{inverse(x.value)}; }

 private:
  static int32_t inverse(int32_t a) {
    int32_t b = P, x = 1, y = 0;
    while (b != 0) {
      auto k = a / b;
      a -= k * b;
      std::swap(a, b);
      x -= k * y;
      std::swap(x, y);
    }
    assert(a == 1);
    if (x < 0) x += P;
    return x;
  }
};

template <int32_t P>
ModInt_t<P> operator+(const ModInt_t<P>& a, const ModInt_t<P>& b) {
  auto res = a;
  return res += b;
};

template <int32_t P>
ModInt_t<P> operator-(const ModInt_t<P>& a, const ModInt_t<P>& b) {
  auto res = a;
  return res -= b;
};

template <int32_t P>
ModInt_t<P> operator*(const ModInt_t<P>& a, const ModInt_t<P>& b) {
  auto res = a;
  return res *= b;
};

template <int32_t P>
bool operator==(const ModInt_t<P>& a, const ModInt_t<P>& b) {
  return a.value == b.value;
};

template <int32_t P>
std::ostream& operator<<(std::ostream& os, const ModInt_t<P>& a) {
  os << a.value;
  return os;
}

template <typename T>
struct MulMonoid {
  using value_type = T;
  constexpr static T identity() { return T{1}; }
  constexpr static T op(const T& a, const T& b) { return a * b; }
};

template <typename T, typename U, typename Monoid = MulMonoid<T>>
T power(T a, U n) {
  T r{Monoid::identity()};
  while (n > 0) {
    if (n % 2) r = Monoid::op(r, a);
    a = Monoid::op(a, a);
    n /= 2;
  }
  return r;
}

using ModInt = ModInt_t<998244353>;

struct ModInverses {
  vector<ModInt> inv;

  ModInverses(int n) : inv(n, ModInt{0}) {
    auto mod = ModInt::mod;
    assert(n < mod);

    inv[1] = ModInt{1};
    for (int i = 2; i < n; ++i) {
      inv[i] = ModInt{0} - ModInt{mod / i} * inv[mod % i];
    }
  };
};

struct Factorial {
  vector<ModInt> fact;
  vector<ModInt> invfact;

  ModInt choose(int n, int k) { return fact[n] * invfact[k] * invfact[n - k]; }

  Factorial(int n) : fact(n, ModInt{0}), invfact(n, ModInt{0}) {
    ModInverses inv(n);

    fact[0] = invfact[0] = ModInt{1};
    for (int i = 1; i < n; ++i) {
      fact[i] = fact[i - 1] * ModInt{i};
      invfact[i] = invfact[i - 1] * inv.inv[i];
    }
  }
};

const int MAX = 303;

bool f[MAX][MAX][MAX];
ModInt g[MAX][MAX][MAX];

int main() {
  std::ios_base::sync_with_stdio(false);

  string S;

  cin >> S;

  int N = S.size();
  vector<vector<int>> minSuf(N + 1, vector<int>(N + 1, -1));

  f[0][0][0] = true;
  for (int i = 0; i <= N; ++i) {
    int c0 = 0, c1 = 0;
    for (int j = i; j < N; ++j) {
      c0 += S[j] == '0';
      c1 += S[j] == '1';
    }

    for (int x = N; x >= 0; --x) {
      for (int y = N; y >= 0; --y) {
        if (f[i][x][y]) {
          minSuf[c0 + x][c1 + y] = max(minSuf[c0 + x][c1 + y], i);

          if (i + 2 <= N) {
            for (int j : {i, i + 1}) {
              int nx = x + (S[j] == '0');
              int ny = y + (S[j] == '1');
              f[i + 2][nx][ny] = true;
            }
          }
          if (i + 1 <= N && x + y >= 1) {
            f[i + 1][x][y] = true;
            if (x > 0 && S[i] == '1') {
              f[i + 1][x - 1][y + 1] = true;
            }
            if (y > 0 && S[i] == '0') {
              f[i + 1][x + 1][y - 1] = true;
            }
          }
          if (x + y >= 2) {
            if (x >= 1) f[i][x - 1][y] = true;
            if (y >= 1) f[i][x][y - 1] = true;
          }
        }
      }
    }
  }

  g[N][0][0] = ModInt{1};
  for (int i = N; i >= 0; --i) {
    for (int x = 0; x <= N; ++x) {
      for (int y = 0; y <= N; ++y) {
        if (i < N && S[i] == '0') {
          g[i][x][y] += g[i + 1][x][y];
        } else if (x > 0) {
          g[i][x][y] += g[i][x - 1][y];
        }

        if (i < N && S[i] == '1') {
          g[i][x][y] += g[i + 1][x][y];
        } else if (y > 0) {
          g[i][x][y] += g[i][x][y - 1];
        }
      }
    }
  }

  Factorial fact(N + 1);

  ModInt ret{0};
  for (int c0 = 0; c0 <= N; ++c0) {
    for (int c1 = 0; c1 <= N; ++c1) {
      if (minSuf[c0][c1] != -1) {
        int s = minSuf[c0][c1];
        int x0 = c0, x1 = c1;
        for (int j = s; j < N; ++j) {
          x0 -= S[j] == '0';
          x1 -= S[j] == '1';
        }
        auto ways = g[s][x0][x1];
        ret += ways;
      }
    }
  }
  cout << ret << "\n";
  return 0;
}