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 MAXN = 300 + 10;
const int MOD = 998244353;

string s;
int n;
bool f[MAXN][MAXN][MAXN];
int a[MAXN][MAXN], dp[MAXN][MAXN][MAXN];

void add(int &a, int b) {
    a = (a + b) % MOD;
}

int main() {
    cin >> s;
    n = s.length();
    
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j <= n; ++j)
            a[i][j] = -1;
            
    f[0][0][0] = true;
    for(int i = 0; i <= s.length(); ++i) {
        int l0 = 0, l1 = 0;
        for(int j = i; j < s.length(); ++j) {
            l0 += (s[j] == '0'); l1 += (s[j] == '1');
        }
        
        for(int sum = s.length(); sum >= 0; --sum)
            for(int n0 = 0; n0 <= sum; ++n0) {
                int n1 = sum - n0;
                if (f[i][n0][n1] == false) continue;
                a[n0 + l0][n1 + l1] = max(a[n0 + l0][n1 + l1], i);
                
                if (sum >= 2) {
                    if (n0 > 0) f[i][n0 - 1][n1] = true;
                    if (n1 > 0) f[i][n0][n1 - 1] = true;
                }
                if (i < s.length() && sum > 0) {
                    f[i + 1][n0][n1] = true;
                    if (n0 > 0) f[i + 1][n0 + (s[i] == '0') - 1][n1 + (s[i] == '1')] = true;
                    if (n1 > 0) f[i + 1][n0 + (s[i] == '0')][n1 + (s[i] == '1') - 1] = true;
                }
                if (i + 1 < s.length()) {
                    f[i + 2][n0 + (s[i] == '0')][n1 + (s[i] == '1')] = true;
                    f[i + 2][n0 + (s[i + 1] == '0')][n1 + (s[i + 1] == '1')] = true;
                }
            }
    }
    
    dp[0][0][s.length()] = 1;
    for(int sum = 0; sum < s.length(); ++sum) {
        for(int n0 = 0; n0 <= sum; ++n0) {
            int n1 = sum - n0;
            for(int i = 0; i <= s.length(); ++i) {
                add(dp[n0 + 1][n1][ i - ((i > 0 && s[i - 1] == '0') ? 1 : 0)], dp[n0][n1][i]);
                add(dp[n0][n1 + 1][ i - ((i > 0 && s[i - 1] == '1') ? 1 : 0)], dp[n0][n1][i]);
            }
        }
    }
    
    int res = 0;
    for(int n0 = 0; n0 <= s.length(); ++n0)
        for(int n1 = 0; n0 + n1 <= s.length(); ++n1) {
            if (a[n0][n1] >= 0) {
                for(int j = 0; j <= a[n0][n1]; ++j) add(res, dp[n0][n1][j]);
            }
        }
        
    cout << res << "\n";
}