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 <cstdio>
#include <cstring>

using namespace std;

const int mod = 998244353;
char s[301];
int a[300];
bool f[301][301][301];
long long dp[301][301][301];

int main() {
    int n, i, j, k;
    long long ans = 1;
    
    scanf("%s", s);
    
    n = strlen(s);
    
    for (i = 0; i < n; i++) a[i] = s[i] - '0';
    
    f[0][0][0] = true;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
                if (!f[i][j][k]) continue;
                
                if (i > 0) {
                    f[i + 1][j][k] = true;
                    
                    if (a[i] == 0 && k > 0) f[i + 1][j + 1][k - 1] = true;
                    if (a[i] == 1 && j > 0) f[i + 1][j - 1][k + 1] = true;
                }
                
                if (i + 2 <= n) {
                    if (a[i] == 0 || a[i + 1] == 0) f[i + 2][j + 1][k] = true;
                    if (a[i] == 1 || a[i + 1] == 1) f[i + 2][j][k + 1] = true;
                }
            }
        }
    }
    
    for (i = 0; i <= n; i++) {
        for (j = n - 1; j >= 0; j--) {
            for (k = n - 1; k >= 0; k--) {
                f[i][j][k] |= f[i][j + 1][k];
                f[i][j][k] |= f[i][j][k + 1];
            }
        }
    }
    
    dp[n][0][0] = 1;
    
    for (i = n; i >= 0; i--) {
        for (j = 0; j < n; j++) {
            for (k = 0; k < n; k++) {
                if (dp[i][j][k] == 0) continue;
                
                if (f[i][j][k]) ans += dp[i][j][k];
                
                if (i == 0) continue;
                
                dp[i - 1][j][k] += dp[i][j][k];
                if (dp[i - 1][j][k] >= mod) dp[i - 1][j][k] -= mod;
                
                if (a[i - 1] == 0) {
                    dp[i][j][k + 1] += dp[i][j][k];
                    if (dp[i][j][k + 1] >= mod) dp[i][j][k + 1] -= mod;
                } else {
                    dp[i][j + 1][k] += dp[i][j][k];
                    if (dp[i][j + 1][k] >= mod) dp[i][j + 1][k] -= mod;
                }
            }
        }
    }
    
    printf("%lld\n", (ans - 1) % mod);
    
    return 0;
}