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 <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <iomanip>
#include <functional>
#include <cassert>

using namespace std;

typedef long long ll;

const int N = 307;
const int md = 998244353;

bool dp[N][N][N];

int cnt[N][N][N][2];

void add(int &a, int b) {
  a += b;
  if (a >= md) a -= md;
}

int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
#endif
  string s;
  cin >> s;
  int n = s.size();
  dp[0][0][0] = 1;
  for (int cnt = 0; cnt < n - 1; ++cnt) {
    for (int a = 0; a < N; ++a) {
      for (int b = 0; b < N; ++b) {
        if (dp[cnt][a][b] == 0) continue;
        int pos = 2 * cnt;
        pos -= cnt - (a + b);
        for (int ta = 0; ta <= min(a, 2); ++ta) {
          for (int tb = 0; tb <= min(b, 2); ++tb) {
            if (ta + tb > 2) continue;
            int ra = ta, rb = tb;
            bool bad = false;
            int cpos = pos;
            while (ra + rb < 2) {
              if (cpos >= n) {
                bad = true;
                break;
              } else {
                if (s[cpos] == '0') ++ra;
                else ++rb;
                ++cpos;
              }
            }
            if (bad) continue;
            if (ra > 0) {
              dp[cnt + 1][a - ta + 1][b - tb] = 1;
            }
            if (rb > 0) {
              dp[cnt + 1][a - ta][b - tb + 1] = 1;
            }
          }
        }
      }
    }
  }
  vector <vector <pair <int, int>>> have(n + 1);
  for (int cnt = 0; cnt <= n - 1; ++cnt) {
    int mx = 0;
    for (int a = 0; a < N; ++a) {
      for (int b = 0; b < N; ++b) {
        if (dp[cnt][a][b] == 0) continue;
        int pos = 2 * cnt;
        pos -= cnt - (a + b);
        have[pos].push_back({a, b});
      }
    }
  }
  for (int i = 0; i <= n; ++i) {
    sort(have[i].begin(), have[i].end());
    have[i].resize(unique(have[i].begin(), have[i].end()) - have[i].begin());
    /*cout << "st " << i << endl;
    for (auto p : have[i]) {
      cout << p.first << ' ' << p.second << endl;
    }
    cout << "ed\n";*/
  }
  cnt[n][0][0][1] = 1;
  for (int i = n; i >= 0; --i) {
    for (int ca = 0; ca <= n; ++ca) {
      for (int cb = 0; cb <= n; ++cb) {
        for (int f = 0; f <= 1; ++f) {
          if (cnt[i][ca][cb][f] == 0) continue;
          if (f == 1) {
            if (i > 0) {
              add(cnt[i - 1][ca][cb][1], cnt[i][ca][cb][1]);
            }
            if (i == 0 || s[i - 1] == '0') {
              add(cnt[i][ca][cb + 1][1], cnt[i][ca][cb][1]);
              if (i > 0) {
                add(cnt[i][ca + 1][cb][0], cnt[i][ca][cb][1]);
              }
            }
            if (i == 0 || s[i - 1] == '1') {
              add(cnt[i][ca + 1][cb][1], cnt[i][ca][cb][1]);
              if (i > 0) {
                add(cnt[i][ca][cb + 1][0], cnt[i][ca][cb][1]);
              }
            }
          } else {
            add(cnt[i][ca + 1][cb][0], cnt[i][ca][cb][0]);
            add(cnt[i][ca][cb + 1][0], cnt[i][ca][cb][0]);
          }
        }
      }
    }
  }
  vector <vector <bool>> used(n + 1, vector <bool> (n + 1));
  int ans = 0;
  int cnt_0 = 0, cnt_1 = 0;
  for (int i = n; i >= 0; --i) {
    if (i < n) {
      if (s[i] == '0') ++cnt_0;
      else ++cnt_1;
    } 
    for (auto p : have[i]) {
      if (used[cnt_0 + p.first][cnt_1 + p.second]) continue;
      used[cnt_0 + p.first][cnt_1 + p.second] = 1;
      add(ans, cnt[i][p.first][p.second][0]);
      add(ans, cnt[i][p.first][p.second][1]);
      /*cout << p.first << ' ' << p.second << endl;
      int sz = n - i + p.first + p.second;
      for (int mask = 0; mask < (1 << sz); ++mask) {
        string t;
        for (int i = 0; i < sz; ++i) {
          if (mask & (1 << i)) {
            t += '1';
          } else {
            t += '0';
          }
        }
        int uk = n - 1;
        int ha = p.first, hb = p.second;
        bool bad = false;
        for (int j = 0; j < (int)t.size(); ++j) {
          if (uk >= i && s[uk] == t[j]) {
            --uk;
            continue;
          }
          if (t[j] == '0') {
            --ha;
          } else {
            --hb;
          }
        }
        if (ha == 0 && hb == 0) {
          cout << "str " << t << endl;
          ++ans;
        }
      } */
    }
  }
  cout << ans << '\n';
}