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 <vector>
#include <cassert>
#include <cmath>

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 300;
int const modulo = 998244353;
int dp[5 + nmax][5 + nmax][5 + nmax];
int pref[5 + nmax][5 + nmax][5 + nmax];

int main() {
  std::string s;
  std::cin >> s;
  int n = s.size();
  s = "0" + s + "0";
  dp[n + 1][0][0] = 1;
  for(int i = n + 1; 1 <= i; i--)
    for(int j = 0; j <= n; j++)
      for(int h = 0; h <= n; h++) {
        if(s[i - 1] == '0') {
          dp[i - 1][j][h] += dp[i][j][h];
          if(modulo <= dp[i - 1][j][h])
            dp[i - 1][j][h] -= modulo;
          dp[i][j][h + 1] += dp[i][j][h];
          if(modulo <= dp[i][j][h + 1])
            dp[i][j][h + 1] -= modulo;
        } else {
          dp[i - 1][j][h] += dp[i][j][h];
          if(modulo <= dp[i - 1][j][h])
            dp[i - 1][j][h] -= modulo;
          dp[i][j + 1][h] += dp[i][j][h];
          if(modulo <= dp[i][j + 1][h])
            dp[i][j + 1][h] -= modulo;
        }
      }
  pref[0][0][0] = 1;
  for(int i = 0;i < n; i++)
    for(int j = 0;j <= n; j++)
      for(int h = 0;h <= n; h++)
        if(0 < pref[i][j][h]) {
          if(s[i + 1] == '0' || s[i + 2] == '0')
            pref[i + 2][j + 1][h] = 1;
          if(s[i + 1] == '1' || s[i + 2] == '1')
            pref[i + 2][j][h + 1] = 1;
          pref[i + 1][j][h] = 1;
          if(s[i + 1] == '0' && 0 < h) 
            pref[i + 1][j + 1][h - 1] = 1;
          if(s[i + 1] == '1' && 0 < j)
            pref[i + 1][j - 1][h + 1] = 1;
        }
  int result = modulo - 1;
  for(int i = 1;i <= n + 1; i++)
    for(int j = 0; j <= n; j++)
      for(int h = 0; h <= n; h++) {
        result += dp[i][j][h] * pref[i - 1][j][h];
        if(modulo <= result)
          result -= modulo;
      }
  std::cout << result ;
  return 0;
}