#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

const int mod = 998244353;

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int maxn = 305;
int c[maxn][maxn];

void precalc() {
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j - 1];
      add(c[i][j], c[i - 1][j]);
    }
  }
}

char tmp[maxn];
int n;
string s;

bool read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  n = sz(s);
  return true;
}

int dp[maxn][maxn][maxn];
int can[maxn][maxn][maxn];

void solve() {
  memset(dp, 0, sizeof(dp));
  dp[n][0][0] = 1;
  for (int i = n - 1; i >= 0; i--) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        auto cur = dp[i + 1][c0][c1];
        if (!cur) {
          continue;
        }
        add(dp[i][c0][c1], cur);
        add(dp[i + 1][c0 + (s[i] == '1')][c1 + (s[i] == '0')], cur);
      }
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    add(dp[i + 1][s[i] == '0'][s[i] == '1'], 1);
  }
  memset(can, 0, sizeof(can));
  can[0][0][0] = 1;
  for (int i = 0; i <= n; i++) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        if (!can[i][c0][c1]) {
          continue;
        }
        if (i + 2 <= n) {
          if (s[i] == '0' || s[i + 1] == '0') {
            can[i + 2][c0 + 1][c1] = true;
          }
          if (s[i] == '1' || s[i + 1] == '1') {
            can[i + 2][c0][c1 + 1] = true;
          }
        }
        if (i < n) {
          for (int take = 0; take < 2; take++) {
            int nc0 = c0 - (take == 0), nc1 = c1 - (take == 1);
            if (nc0 < 0 || nc1 < 0) {
              continue;
            }
            if (s[i] == '0' || take == 0) {
              can[i + 1][nc0 + 1][nc1] = true;
            }
            if (s[i] == '1' || take == 1) {
              can[i + 1][nc0][nc1 + 1] = true;
            }
          }
        }
        for (int take0 = 0; take0 < 2; take0++) {
          int nc0 = c0 - (take0 == 0), nc1 = c1 - (take0 == 1);
          if (nc0 < 0 || nc1 < 0) {
            continue;
          }
          for (int take1 = 0; take1 < 2; take1++) {
            int nnc0 = nc0 - (take1 == 0), nnc1 = nc1 - (take1 == 1);
            if (nnc0 < 0 || nnc1 < 0) {
              continue;
            }
            if (take0 == 0 || take1 == 0) {
              can[i][nnc0 + 1][nnc1] = true;
            }
            if (take0 == 1 || take1 == 1) {
              can[i][nnc0][nnc1 + 1] = true;
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i <= n; i++) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        if (can[i][c0][c1]) {
          add(res, dp[i][c0][c1]);
        }
      }
    }
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

const int mod = 998244353;

int mul(int a, int b) {
  return (long long) a * b % mod;
}

void add(int &a, int b) {
  a += b;
  if (a >= mod) {
    a -= mod;
  }
}

const int maxn = 305;
int c[maxn][maxn];

void precalc() {
  for (int i = 0; i < maxn; i++) {
    c[i][0] = 1;
    for (int j = 1; j <= i; j++) {
      c[i][j] = c[i - 1][j - 1];
      add(c[i][j], c[i - 1][j]);
    }
  }
}

char tmp[maxn];
int n;
string s;

bool read() {
  if (scanf("%s", tmp) < 1) {
    return false;
  }
  s = tmp;
  n = sz(s);
  return true;
}

int dp[maxn][maxn][maxn];
int can[maxn][maxn][maxn];

void solve() {
  memset(dp, 0, sizeof(dp));
  dp[n][0][0] = 1;
  for (int i = n - 1; i >= 0; i--) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        auto cur = dp[i + 1][c0][c1];
        if (!cur) {
          continue;
        }
        add(dp[i][c0][c1], cur);
        add(dp[i + 1][c0 + (s[i] == '1')][c1 + (s[i] == '0')], cur);
      }
    }
  }
  for (int i = n - 1; i >= 0; i--) {
    add(dp[i + 1][s[i] == '0'][s[i] == '1'], 1);
  }
  memset(can, 0, sizeof(can));
  can[0][0][0] = 1;
  for (int i = 0; i <= n; i++) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        if (!can[i][c0][c1]) {
          continue;
        }
        if (i + 2 <= n) {
          if (s[i] == '0' || s[i + 1] == '0') {
            can[i + 2][c0 + 1][c1] = true;
          }
          if (s[i] == '1' || s[i + 1] == '1') {
            can[i + 2][c0][c1 + 1] = true;
          }
        }
        if (i < n) {
          for (int take = 0; take < 2; take++) {
            int nc0 = c0 - (take == 0), nc1 = c1 - (take == 1);
            if (nc0 < 0 || nc1 < 0) {
              continue;
            }
            if (s[i] == '0' || take == 0) {
              can[i + 1][nc0 + 1][nc1] = true;
            }
            if (s[i] == '1' || take == 1) {
              can[i + 1][nc0][nc1 + 1] = true;
            }
          }
        }
        for (int take0 = 0; take0 < 2; take0++) {
          int nc0 = c0 - (take0 == 0), nc1 = c1 - (take0 == 1);
          if (nc0 < 0 || nc1 < 0) {
            continue;
          }
          for (int take1 = 0; take1 < 2; take1++) {
            int nnc0 = nc0 - (take1 == 0), nnc1 = nc1 - (take1 == 1);
            if (nnc0 < 0 || nnc1 < 0) {
              continue;
            }
            if (take0 == 0 || take1 == 0) {
              can[i][nnc0 + 1][nnc1] = true;
            }
            if (take0 == 1 || take1 == 1) {
              can[i][nnc0][nnc1 + 1] = true;
            }
          }
        }
      }
    }
  }
  int res = 0;
  for (int i = 0; i <= n; i++) {
    for (int c0 = 0; c0 <= n; c0++) {
      for (int c1 = 0; c1 <= n; c1++) {
        if (can[i][c0][c1]) {
          add(res, dp[i][c0][c1]);
        }
      }
    }
  }
  printf("%d\n", res);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}

```