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 <bits/stdc++.h>

using namespace std;

const int mod = 998244353;
inline int pls( int a , int b ) { a += b - mod; return a + ( a >> 31 & mod ); }
inline int mns( int a , int b ) { a -= b; return a + ( a >> 31 & mod ); }
inline void inc( int & a , int b ) { a += b - mod; a += a >> 31 & mod; }
inline void dec( int & a , int b ) { a -= b; a += a >> 31 & mod; }
inline int fpow( int base , int k ) {
  int res = 1;
  while( k ) {
    if( k & 1 ) res = (long long)res * base % mod;
    base = (long long)base * base % mod; k >>= 1;
  }
  return res;
} int _w;

const int N = 3e2 + 5;

char str[N];
bool g[N][N][N];
int f[N][N][N] , n;

int main( void ) {
  _w = scanf("%s",str+1); 
  n = strlen( str + 1 );
  f[n + 1][0][0] = 1;
  for( int i = n ; i ; --i )
    for( int j = 0 ; j <= n - i ; ++j )
      for( int k = 0 ; j + k <= n - i ; ++k ) {
        inc( f[i][j][k] , f[i + 1][j][k] );
        if( str[i + j + k] == '0' ) 
          inc( f[i][j + 1][k] , f[i + 1][j][k] );
        else inc( f[i][j][k + 1] , f[i + 1][j][k] );
      }
  g[0][0][0] = 1;
  for( int i = 1 ; i <= n ; ++i ) {
    for( int j = 0 ; j <= i ; ++j )
      for( int k = 0 , a , b ; j + k <= i ; ++k ) {
        g[i][j][k] |= g[i - 1][j][k];
        if( i > 1 ) {
          a = str[i - 1] - '0' , b = str[i] - '0';
          if( a || b ) g[i][j + 1][k] |= g[i - 2][j][k];
          if( !(a&b) ) g[i][j][k + 1] |= g[i - 2][j][k];
        }
        if( str[i] == '1' )
          g[i][j + 1][k] |= g[i - 1][j][k + 1];
        else
          g[i][j][k + 1] |= g[i - 1][j + 1][k];
      }
  }
  int ans = 0;
  for( int i = 0 ; i <= n ; ++i )
    for( int j = 0 ; j <= i ; ++j )
      for( int k = 0 ; k + j <= i ; ++k )
        if( g[i][j][k] )
          inc( ans , f[i + 1 - j - k][j][k] );
  dec( ans , 1 );
  printf("%d\n",ans);
  return 0;
}