#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<998244353>;

bool can[330][330][330];
Mint dp[330][330][330];

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   string S; cin >> S;
   int N = S.size();
   for (int i = 0; i < N; ++i) {
      can[i][0][0] = true;
      for (int n0 = 0; n0 <= i; ++n0) {
         for (int n1 = 0; n1 <= i; ++n1) {
            if (!can[i][n0][n1]) continue;
            if (i) can[i + 1][n0][n1] = true;
            if (n0) {
               int nn0 = n0 - 1 + (S[i] == '0');
               int nn1 = n1 + (S[i] == '1');
               can[i + 1][nn0][nn1] = true;
            }
            if (n1) {
               int nn0 = n0 + (S[i] == '0');
               int nn1 = n1 - 1 + (S[i] == '1');
               can[i + 1][nn0][nn1] = true;
            }
            if (i + 1 < N) {
               can[i + 2][n0 + (S[i] == '0')][n1 + (S[i] == '1')] = true;
               can[i + 2][n0 + (S[i + 1] == '0')][n1 + (S[i + 1] == '1')] = true;
            }
         }
      }
   }
   can[N][0][0] = false;
   Mint ans = 0;
   dp[N][0][0] = 1;
   for (int i = N; i >= 0; --i) {
      for (int n0 = 0; n0 <= N; ++n0) {
         for (int n1 = 0; n1 <= N; ++n1) {
            // if (dp[i][n0][n1].val == 0) continue;
            if (can[i][n0][n1]) ans += dp[i][n0][n1];

            if (i > 0 && S[i - 1] == '0') {
               dp[i - 1][n0][n1] += dp[i][n0][n1];
            } else {
               dp[i][n0 + 1][n1] += dp[i][n0][n1];
            }

            if (i > 0 && S[i - 1] == '1') {
               dp[i - 1][n0][n1] += dp[i][n0][n1];
            } else {
               dp[i][n0][n1 + 1] += dp[i][n0][n1];
            }
         }
      }
   }
   cout << ans << "\n";
   return 0;
}

### Prompt

Create a solution in CPP for the following 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

### Response

```cpp
#include <bits/stdc++.h>

using namespace std;

using ll = long long;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<998244353>;

bool can[330][330][330];
Mint dp[330][330][330];

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   string S; cin >> S;
   int N = S.size();
   for (int i = 0; i < N; ++i) {
      can[i][0][0] = true;
      for (int n0 = 0; n0 <= i; ++n0) {
         for (int n1 = 0; n1 <= i; ++n1) {
            if (!can[i][n0][n1]) continue;
            if (i) can[i + 1][n0][n1] = true;
            if (n0) {
               int nn0 = n0 - 1 + (S[i] == '0');
               int nn1 = n1 + (S[i] == '1');
               can[i + 1][nn0][nn1] = true;
            }
            if (n1) {
               int nn0 = n0 + (S[i] == '0');
               int nn1 = n1 - 1 + (S[i] == '1');
               can[i + 1][nn0][nn1] = true;
            }
            if (i + 1 < N) {
               can[i + 2][n0 + (S[i] == '0')][n1 + (S[i] == '1')] = true;
               can[i + 2][n0 + (S[i + 1] == '0')][n1 + (S[i + 1] == '1')] = true;
            }
         }
      }
   }
   can[N][0][0] = false;
   Mint ans = 0;
   dp[N][0][0] = 1;
   for (int i = N; i >= 0; --i) {
      for (int n0 = 0; n0 <= N; ++n0) {
         for (int n1 = 0; n1 <= N; ++n1) {
            // if (dp[i][n0][n1].val == 0) continue;
            if (can[i][n0][n1]) ans += dp[i][n0][n1];

            if (i > 0 && S[i - 1] == '0') {
               dp[i - 1][n0][n1] += dp[i][n0][n1];
            } else {
               dp[i][n0 + 1][n1] += dp[i][n0][n1];
            }

            if (i > 0 && S[i - 1] == '1') {
               dp[i - 1][n0][n1] += dp[i][n0][n1];
            } else {
               dp[i][n0][n1 + 1] += dp[i][n0][n1];
            }
         }
      }
   }
   cout << ans << "\n";
   return 0;
}

```