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 <iostream>
#include <cstring>
#include <cstdio>
#define MN 300
#define mod 998244353
using namespace std;
int n;
char s[MN + 5];
/*
  f:
  (from the end) length = i, has inserted j '0' and k '1', i.e. keep the last i - j - k bits of the original sequence
  how many (different) possible sequences
  note that j,k are the minimum number of bits to insert
*/
int f[MN + 5][MN + 5][MN + 5]; 
/*
  g:
  has performed i deletion, whether possible to insert j '0' and k '1' into the latter part
*/
bool g[MN + 5][MN + 5][MN + 5];
int num0[MN + 5], Max[MN + 5];

inline void R(int &x, int y) {
  (x += y) >= mod ? x -= mod : 0;
}

int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = n; i; --i) {
    num0[i] = num0[i + 1] + (s[i] == '0');
  }
  // first part: f
  f[0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0 ; j < i; ++j) {
      for (int k = 0; k < i - j; ++k) {
        int t = s[n - i + 1 + j + k] - '0'; // current position in s
        // if we want a t, then we should not insert (to minimize the number of insertion).
        R(f[i][j][k], f[i - 1][j][k]);
        // if we want a different bit(!t), then we should insert.
        R(f[i][j + t][k + (!t)], f[i - 1][j][k]);
      }
    }
  }
  // second part: g
  g[0][0][0] = 1;
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < i; ++j) {
      for (int k = 0; k < i - j; ++k) {
        if (!g[i - 1][j][k]) continue;
        //printf("possible g: %d %d %d\n", i - 1, j, k);
        int pos = i + j + k; // current position if we want to delete
        if (pos < n) { // possible to delete 2 bits
          int num0 = (s[pos] == '0') + (s[pos + 1] == '0');
          int num1 = 2 - num0;
          /* 
            possible action:
            *  keep one bit for insertion
            *  use 1 bit that kept before and keep another bit
            *  use 2 bit that kept before and keep one of them
          */
          if (num0) g[i][j + 1][k] = 1;
          if (num1) g[i][j][k + 1] = 1;
        }
        if (pos <= n) { // possible to delete 1 bit
          if (j && s[pos] == '1') {
            g[i][j - 1][k + 1] = 1;
          } else if (k && s[pos] == '0') {
            g[i][j + 1][k - 1] = 1;
          }
          if (j|k) g[i][j][k] = 1;
        }
        if (j >= 2) g[i][j - 1][k] = 1;
        if (k >= 2) g[i][j][k - 1] = 1;
      }
    }
  }
  // calculate the answer
  int ans = 0;
  for (int length = 1; length <= n; ++length) {
    memset(Max, -1, sizeof(Max));
    // if we can get one by insert j '0' and k '1'
    // then we can also get it by insert more '0' and '1'
    // as long as the number of '0' and '1' is correct
    for (int j = length; ~j; --j) {
      for (int k = length - j; ~k; --k) {
        int now_num0 = num0[n - length + 1 + j + k] + j;
        if (g[n - length][j][k]) {
          Max[now_num0] = max(Max[now_num0], k);
        }
        if (Max[now_num0] >= k) {
          R(ans, f[length][j][k]);
        }
      }
    }
  }
  cout << ans;
  return 0;
}