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>

constexpr int N = 300, P = 998244353;

int n;
std::string s;

int dp[N + 1][N + 1][N + 1], g[N + 1][N + 1][N + 1];

void chkmax(int &a, int b) {
    a = std::max(a, b);
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    std::cin >> s;
    n = s.length();
    
    std::memset(g, -1, sizeof(g));
    
    g[0][0][0] = 0;
    
    for (int j = 0; j < n; ++j) {
        for (int i = 0; i <= j; ++i) {
            for (int k = 0; k <= j - i; ++k) {
                if (g[i][j][k] < 0)
                    continue;
                chkmax(g[i + 1][j + 1][k], g[i][j][k]);
                chkmax(g[i][j + 1][k + (s[j] == '0')], g[i][j][k] - 1);
                if (j + 2 <= n) {
                    chkmax(g[i + 2][j + 2][k], g[i][j][k] + 1);
                    chkmax(g[i + 1][j + 2][k + (s[j] == '0')], g[i][j][k]);
                    chkmax(g[i + 1][j + 2][k + (s[j + 1] == '0')], g[i][j][k]);
                }
            }
        }
    }
    
    dp[n][n][0] = 1;
    
    int ans = 0;
    for (int i = n - 1; i >= 0; --i) {
        for (int j = i; j <= n; ++j) {
            for (int k = 0; k <= j - i; ++k) {
                if (j < n)
                    dp[i][j][k] += dp[i + 1][j + 1][k];
                if (j > i && k - (s[j - 1] - '0') >= 0)
                    dp[i][j][k] += dp[i + 1][j][k - (s[j - 1] - '0')];
                if (dp[i][j][k] >= P)
                    dp[i][j][k] -= P;
                if (dp[i][j][k] && g[i][j][k] >= 0) {
                    ans += dp[i][j][k];
                    if (ans >= P)
                        ans -= P;
                }
            }
        }
    }
    
    std::cout << ans << "\n";
    
    return 0;
}