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 md=998244353;
struct Modint {
  int x;
  Modint() { x=0; }
  Modint(int v) { x=v; }
  Modint operator+=(const Modint& oth) {
    x+=oth.x;
    if (x>=md) x-=md;
    return *this;
  }
} dp[302][302][302],r;
int n,i,j,k,is0;
bool f[302][302][302];
char s[302];
int main() {
  scanf("%s",s);
  n=strlen(s);
  f[0][0][0]=true;
  for (i=0; i<n; i++) for (j=i; j>=0; j--) for (k=i-j; k>=0; k--) if (f[i][j][k]) {
    is0=int(s[i]=='0');
    if (j+k>1) {
      if (j>0) f[i][j-1][k]=true;
      if (k>0) f[i][j][k-1]=true;
    }
    if (j+k>0 || i+1<n) f[i+1][j][k]=true;
    if (j>0) f[i+1][j-1+is0][k+1-is0]=true;
    if (k>0) f[i+1][j+is0][k-is0]=true;
    if (i+1<n) {
      f[i+2][j+is0][k+1-is0]=true;
      is0=int(s[i+1]=='0');
      f[i+2][j+is0][k+1-is0]=true;
    }
  }
  dp[n][0][0]=1;
  for (i=n; i>=0; i--) for (j=0; j<=n; j++) for (k=0; k<=n; k++) if (dp[i][j][k].x) {
  //printf("%d %d %d = %d [%d]\n",i,j,k,dp[i][j][k].x,f[i][j][k]);
    if (f[i][j][k]) r+=dp[i][j][k];
    if (i==0) continue;
    is0=int(s[i-1]=='0');
    dp[i-1][j][k]+=dp[i][j][k];
    dp[i][j+1-is0][k+is0]+=dp[i][j][k];
  }
  printf("%d\n",r.x);
  return 0;
}