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 <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

//#define debug(x) ;
#define debug(x) cerr << #x << " = " << x << "\n";

ostream& operator<<(ostream& cerr, vector<ll> aux) {
  cerr << "[";
  for (auto e : aux) cerr << e << ' ';
  cerr << "]";
  return cerr;
}

const int maxN = 311;
const int mod = 998244353;

int n;
char s[maxN];

bool reachable[maxN][maxN][maxN];
bool deny[maxN][maxN][maxN];
int dp[maxN][maxN][maxN][2];


void upd(int& dest, int sour, int coef = 1) {
  dest += (1LL * sour * coef) % mod;
  if (dest >= mod) dest -= mod;
}

void computeReachable() {
  reachable[0][0][0] = 1;

  for (int i = 0; i < n; i++) {
    bool nextZero = s[i + 1] == '0';

    for (int zeros = 0; zeros <= i; zeros++) {
      for (int ones = 0; ones <= i; ones++) {
        if (!reachable[i][zeros][ones]) continue;
 
        // Use next 2
        if (i + 2 <= n) {
          bool nextZero2 = s[i + 2] == '0';

          if (nextZero == nextZero2) {
            if (nextZero)
              reachable[i + 2][zeros + 1][ones] = true;
            else
              reachable[i + 2][zeros][ones + 1] = true;
          } else {
            reachable[i + 2][zeros + 1][ones] = true;
            reachable[i + 2][zeros][ones + 1] = true;
          }
        }

        // Cut next element
        if (ones + zeros > 0)
          reachable[i + 1][zeros][ones] = true;

        // Exchange one for zero
        if (nextZero && ones > 0) 
          reachable[i + 1][zeros + 1][ones - 1] = true; 

        // Exchange zero for one
        if (!nextZero && zeros > 0) 
          reachable[i + 1][zeros - 1][ones + 1] = true;
      }
    }
  }
}

void computeDeny() {
  for (int i = n; i > 0; i--) {
    for (int zeros = 0; zeros <= i; zeros++) {
      for (int ones = 0; ones <= i; ones++) {
        bool propagate = deny[i][zeros][ones] || reachable[i][zeros][ones];

        if (s[i] == '0') {
          if (zeros > 0)
            deny[i - 1][zeros - 1][ones] |= propagate;
        } else {
          if (ones > 0)
            deny[i - 1][zeros][ones - 1] |= propagate;
        }
      }
    }
  }
}

void computeDP() {
  dp[n][0][0][0] = 1;

  for (int i = n; i >= 0; i--) {
    bool nextZero = (s[i] == '0' ? true : false);

    // Use next char if possible
    if (i > 0) {
      for (int zeros = 0; zeros <= i; zeros++) {
        for (int ones = 0; ones <= i; ones++) {
          
          // Use next char
          upd(dp[i - 1][zeros][ones][0], dp[i][zeros][ones][0]);
          upd(dp[i - 1][zeros][ones][0], dp[i][zeros][ones][1]);
          
          if (nextZero) {
            // add virtual one
            upd(dp[i][zeros][ones + 1][1], dp[i][zeros][ones][0]);
            upd(dp[i][zeros][ones + 1][1], dp[i][zeros][ones][1]);
          } else {
            // add virtual zero
            upd(dp[i][zeros + 1][ones][1], dp[i][zeros][ones][0]);
            upd(dp[i][zeros + 1][ones][1], dp[i][zeros][ones][1]);
          } 
        }
      }
    }

    // Add virtual head
    for (int zeros = 0; zeros <= i; zeros++) {
      for (int ones = 0; ones <= i; ones++) {
        upd(dp[i][zeros + 1][ones][0], dp[i][zeros][ones][0]);
        upd(dp[i][zeros][ones + 1][0], dp[i][zeros][ones][0]);
      }
    }
  }
}

int main()
{
  //freopen("test.in", "r", stdin);

  scanf("%s", s + 1);
  n = strlen(s + 1);

  cerr << "Start computing..\n";
  computeReachable();
  cerr << "Computed reachable..\n";
  computeDeny();
  cerr << "Computed deny..\n";
  computeDP();
  cerr << "Computed dp..\n";

  if (false)
  for (int i = 0; i <= n; i++) {
    cerr << "For " << i << '\n';
    for (int zeros = 0; zeros <= i; zeros++) {
      for (int ones = 0; ones <= i; ones++) {
        cerr << '(' << reachable[i][zeros][ones] << 
                ", " << deny[i][zeros][ones] <<
                ", " << dp[i][zeros][ones][0] << ") ";
      }
      cerr << '\n';
    }
  }

  int answer = 0;
  for (int i = 0; i <= n; i++) 
    for (int zeros = 0; zeros <= i; zeros++)
      for (int ones = 0; ones <= i; ones++)
        if (reachable[i][zeros][ones])
          if (!deny[i][zeros][ones])
            upd(answer, dp[i][zeros][ones][0]);

  cout << answer;

  return 0;
}