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;

#define int long long
#undef int 

const int MOD = 998244353; 
int choose [1005][1005]; 

int s [305]; 

int dp [305][305][305]; 
bool can_make [305][305][305]; 

int main(){
    #define int long long
    ios_base::sync_with_stdio(0); 

    for (int i=0; i<=1000; i++) choose[i][0] = 1; 
    for (int i=1; i<=1000; i++){
        for (int j=1; j<=1000; j++){
            choose[i][j] = choose[i-1][j-1] + choose[i-1][j]; 
            choose[i][j] %= MOD; 
        }
    }

    string x; cin >> x; 
    for (int i=1; i<=(int)x.length(); i++) s[i] = x[i-1]-'0'; 
    int tot0=0,tot1=0; 
    for (int i=1; i<=(int)x.length(); i++){
        if(s[i])tot1++;
        else tot0++;
    }

    int n = (int)x.length(); 

    for (int i=0; i<=300; i++){
        for (int j=0; j<=300; j++){
            dp[n + 1][i][j] = choose[i + j][j]; 
        }
    }
    for (int i=n; i>=1; i--){
        for (int j=0; j<=300; j++){ // num zero
            for (int k=0; k<=300; k++){ // num one
                if (s[i]==1){
                    dp[i][j][k] += dp[i + 1][j][k]; 
                    if (j > 0) dp[i][j][k] += dp[i][j - 1][k]; 
                    dp[i][j][k] %= MOD; 
                }
                else{
                    dp[i][j][k] += dp[i + 1][j][k]; 
                    if (k > 0) dp[i][j][k] += dp[i][j][k - 1]; 
                    dp[i][j][k] %= MOD;                     
                }
            }
        }
    }
    can_make[0][0][0] = 1; 
    for (int i=1; i<=n; i++){
        for (int j=0; j<=300; j++){
            for (int k=0; k<=300; k++){
                can_make[i][j][k] = can_make[i - 1][j][k]; 
                if ((!s[i]) && j)
                    can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 1][j - 1][k + 1]);
                if ((s[i]) && k)
                    can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 1][j + 1][k - 1]);
                if (i >= 2){
                    if ((!s[i]) && j)
                        can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 2][j - 1][k]);
                    if ((s[i]) && k)
                        can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 2][j][k - 1]);                    
                    if ((!s[i - 1]) && j)
                        can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 2][j - 1][k]);
                    if ((s[i - 1]) && k)
                        can_make[i][j][k] = max(can_make[i][j][k], can_make[i - 2][j][k - 1]);        
                }
            }
        }
    }
    int ans=0; 
    for (int i=0; i<=300; i++){
        for (int j=0; j<=300; j++){
            int num0=0,num1=0; 
            int ind=-1,ind2=-1,ind3=-1; 
            for (int k=1; k<=n+1; k++){
                int num0_right = tot0 - num0; 
                int num1_right = tot1 - num1; 
                if (num0_right <= i && num1_right <= j){ 
                    int num0_left = i - num0_right; 
                    int num1_left = j - num1_right; 
                    if (num0_left <= num0 && num1_left <= num1){
                        if (num0 + num1 == 0 || (num0_left + num1_left > 0)){
                            if (can_make[k - 1][num0_left][num1_left]){
                                ind=k, ind2=num0_left, ind3=num1_left; 
                            }
                        }
                    }
                }
                if (k <= n){
                    if (s[k]) num1++; 
                    else num0++; 
                }
            }
            if (ind!=-1){
                ans += dp[ind][ind2][ind3]; 
                ans %= MOD;
            }
        }
    }

    cout << ans << '\n'; 

    return 0; 
}