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;

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;
             //cout<<i<<' '<<n1<<' '<<n0<<' '<<dp[i][n0][n1].val<<endl;
            if (can[i][n0][n1])
            {
                ans += dp[i][n0][n1];
            }
            if (i>0)
            {
                dp[i-1][n0][n1]+=dp[i][n0][n1];
                if(S[i - 1] == '1')
                    dp[i][n0 + 1][n1] += dp[i][n0][n1];
                else dp[i][n0][n1 + 1] += dp[i][n0][n1];
            }
         }
      }
   }
   cout << ans << "\n";
   return 0;
}
/*
000110
6 0 0 1
6 1 0 1
6 2 0 1
6 3 0 1
6 4 0 1
6 5 0 1
6 6 0 1
5 0 0 1
5 1 0 1
5 2 0 1
5 3 0 1
5 4 0 1
5 5 0 1
5 6 0 1
5 0 1 1
5 1 1 1
5 2 1 1
5 3 1 1
5 4 1 1
5 5 1 1
5 6 1 1
5 0 2 1
5 1 2 1
5 2 2 1
5 3 2 1
5 4 2 1
5 5 2 1
5 6 2 1
5 0 3 1
5 1 3 1
5 2 3 1
5 3 3 1
5 4 3 1
5 5 3 1
5 6 3 1
5 0 4 1
5 1 4 1
5 2 4 1
5 3 4 1
5 4 4 1
5 5 4 1
5 6 4 1
5 0 5 1
5 1 5 1
5 2 5 1
5 3 5 1
5 4 5 1
5 5 5 1
5 6 5 1
5 0 6 1
5 1 6 1
5 2 6 1
5 3 6 1
5 4 6 1
5 5 6 1
5 6 6 1
4 0 0 1
4 1 0 1
4 2 0 1
4 3 0 1
4 4 0 1
4 5 0 1
4 6 0 1
4 0 1 2
4 1 1 2
4 2 1 2
4 3 1 2
4 4 1 2
4 5 1 2
4 6 1 2
4 0 2 3
4 1 2 3
4 2 2 3
4 3 2 3
4 4 2 3
4 5 2 3
4 6 2 3
4 0 3 4
4 1 3 4
4 2 3 4
4 3 3 4
4 4 3 4
4 5 3 4
4 6 3 4
4 0 4 5
4 1 4 5
4 2 4 5
4 3 4 5
4 4 4 5
4 5 4 5
4 6 4 5
4 0 5 6
4 1 5 6
4 2 5 6
4 3 5 6
4 4 5 6
4 5 5 6
4 6 5 6
4 0 6 7
4 1 6 7
4 2 6 7
4 3 6 7
4 4 6 7
4 5 6 7
4 6 6 7
3 0 0 1
3 1 0 2
3 2 0 3
3 3 0 4
3 4 0 5
3 5 0 6
3 6 0 7
3 0 1 2
3 1 1 4
3 2 1 6
3 3 1 8
3 4 1 10
3 5 1 12
3 6 1 14
3 0 2 3
3 1 2 6
3 2 2 9
3 3 2 12
3 4 2 15
3 5 2 18
3 6 2 21
3 0 3 4
3 1 3 8
3 2 3 12
3 3 3 16
3 4 3 20
3 5 3 24
3 6 3 28
3 0 4 5
3 1 4 10
3 2 4 15
3 3 4 20
3 4 4 25
3 5 4 30
3 6 4 35
3 0 5 6
3 1 5 12
3 2 5 18
3 3 5 24
3 4 5 30
3 5 5 36
3 6 5 42
3 0 6 7
3 1 6 14
3 2 6 21
3 3 6 28
3 4 6 35
3 5 6 42
3 6 6 49
2 0 0 1
2 1 0 3
2 2 0 6
2 3 0 10
2 4 0 15
2 5 0 21
2 6 0 28
2 0 1 2
2 1 1 6
2 2 1 12
2 3 1 20
2 4 1 30
2 5 1 42
2 6 1 56
2 0 2 3
2 1 2 9
2 2 2 18
2 3 2 30
2 4 2 45
2 5 2 63
2 6 2 84
2 0 3 4
2 1 3 12
2 2 3 24
2 3 3 40
2 4 3 60
2 5 3 84
2 6 3 112
2 0 4 5
2 1 4 15
2 2 4 30
2 3 4 50
2 4 4 75
2 5 4 105
2 6 4 140
2 0 5 6
2 1 5 18
2 2 5 36
2 3 5 60
2 4 5 90
2 5 5 126
2 6 5 168
2 0 6 7
2 1 6 21
2 2 6 42
2 3 6 70
2 4 6 105
2 5 6 147
2 6 6 196
1 0 0 1
1 1 0 4
1 2 0 10
1 3 0 20
1 4 0 35
1 5 0 56
1 6 0 84
1 0 1 2
1 1 1 8
1 2 1 20
1 3 1 40
1 4 1 70
1 5 1 112
1 6 1 168
1 0 2 3
1 1 2 12
1 2 2 30
1 3 2 60
1 4 2 105
1 5 2 168
1 6 2 252
1 0 3 4
1 1 3 16
1 2 3 40
1 3 3 80
1 4 3 140
1 5 3 224
1 6 3 336
1 0 4 5
1 1 4 20
1 2 4 50
1 3 4 100
1 4 4 175
1 5 4 280
1 6 4 420
1 0 5 6
1 1 5 24
1 2 5 60
1 3 5 120
1 4 5 210
1 5 5 336
1 6 5 504
1 0 6 7
1 1 6 28
1 2 6 70
1 3 6 140
1 4 6 245
1 5 6 392
1 6 6 588
0 0 0 1
0 1 0 4
0 2 0 10
0 3 0 20
0 4 0 35
0 5 0 56
0 6 0 84
0 0 1 2
0 1 1 8
0 2 1 20
0 3 1 40
0 4 1 70
0 5 1 112
0 6 1 168
0 0 2 3
0 1 2 12
0 2 2 30
0 3 2 60
0 4 2 105
0 5 2 168
0 6 2 252
0 0 3 4
0 1 3 16
0 2 3 40
0 3 3 80
0 4 3 140
0 5 3 224
0 6 3 336
0 0 4 5
0 1 4 20
0 2 4 50
0 3 4 100
0 4 4 175
0 5 4 280
0 6 4 420
0 0 5 6
0 1 5 24
0 2 5 60
0 3 5 120
0 4 5 210
0 5 5 336
0 6 5 504
0 0 6 7
0 1 6 28
0 2 6 70
0 3 6 140
0 4 6 245
0 5 6 392
0 6 6 588
*/