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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cctype>

#include <algorithm>
#include <random>
#include <bitset>
#include <queue>
#include <functional>
#include <set>
#include <map>
#include <vector>
#include <chrono>
#include <iostream>
#include <limits>
#include <numeric>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

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

template<class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (T &x : v)
    is >> x;
  return is;
}

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

const int P = 998244353;

int norm(int x) { return x >= P ? (x - P) : x; }

void add(int &x, int y) { if ((x += y) >= P) x -= P; }

void sub(int &x, int y) { if ((x -= y) < 0) x += P; }

void exGcd(int a, int b, int &x, int &y) {
  if (!b) {
    x = 1;
    y = 0;
    return;
  }
  exGcd(b, a % b, y, x);
  y -= a / b * x;
}

int inv(int a) {
  int x, y;
  exGcd(a, P, x, y);
  return norm(x + P);
}

const int N = 310;

char s[N];
int n0, n1;
int s0[N], s1[N];
int p0[N], p1[N];
int dp[N][N], f[N][N][N];
int len[N][N][N];

int main() {
#ifdef ELEGIA
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> s;
  int n = strlen(s);
  for (int i = 0; i < n; ++i)
    if (s[i] == '0')
      p0[n0++] = i;
    else
      p1[n1++] = i;
  for (int i = 0; i < n; ++i) {
    s0[i + 1] = s0[i] + (s[i] == '0');
    s1[i + 1] = s1[i] + (s[i] == '1');
  }
  dp[0][0] = 1;
  for (int i = 0; i <= n; ++i) {
    memcpy(f[i], dp, sizeof(dp));
    for (int j = 0; j <= n0; ++j)
      for (int k = 0; k <= n1; ++k) {
        add(f[i][j][k + 1], f[i][j][k]);
        add(f[i][j + 1][k], f[i][j][k]);
      }
    if (i == n) break;
    for (int j = 0; j <= n0; ++j)
      for (int k = 0; k <= n1; ++k) {
        if (s[n - 1 - i] == '0')
          add(dp[j][k + 1], dp[j][k]);
        else
          add(dp[j + 1][k], dp[j][k]);
      }
  }

  memset(len, -1, sizeof(len));
  len[0][0][0] = 0;
  for (int i = 0; i <= n0; ++i) {
    for (int j = 0; j <= n1; ++j) {
      for (int k = i + j; k >= 0; --k) {
        if (len[i][j][k] == -1) continue;
        if (k) {
          len[i][j][k - 1] = max(len[i][j][k - 1], len[i][j][k] + 1);
        }
        int c0 = 0, c1 = 0;
        for (int t = 0; t < 2 && len[i][j][k] + t < n; ++t) {
          if (s[len[i][j][k] + t] == '0') ++c0;
          else ++c1;
        }
        if (c0 == 2) {
          len[i + 2][j][k + 1] = max(len[i + 2][j][k + 1], len[i][j][k] + 2);
        }
        if (c1 == 2) {
          len[i][j + 2][k + 1] = max(len[i][j + 2][k + 1], len[i][j][k] + 2);
        }
        if (c0 && c1)
          len[i + 1][j + 1][k + 1] = max(len[i + 1][j + 1][k + 1], len[i][j][k] + 2);
        if (c0)
          len[i + 1][j][k] = max(len[i + 1][j][k], len[i][j][k] + 2);
        if (c1)
          len[i][j + 1][k] = max(len[i][j + 1][k], len[i][j][k] + 2);
      }
    }
  }

  int ans = 0;
  for (int i = 0; i <= n0; ++i)
    for (int j = 0; j <= n1; ++j) {
      if (i + j == n) continue;
      int al = len[i][j][0];
      if (al == -1) continue;

      al = min(al, n);
      add(ans, f[n - al][s0[al] - i][s1[al] - j]);
    }
  cout << ans << '\n';

#ifdef ELEGIA
  LOG("Time: %dms\n", int ((clock()
          -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}