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;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=305,INF=1<<30;
bool dp[MAX][MAX][MAX];
ll dp2[MAX][MAX][MAX];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    string S;cin>>S;
    int N=si(S);
    dp[0][0][0]=1;
    
    for(int i=0;i<N;i++){
        for(int j=N;j>=0;j--){
            for(int k=N;k>=0;k--){
                if(dp[i][j][k]==0) continue;
                
                if(i+1<N){
                    if(S[i]=='0') dp[i+2][j+1][k]=1;
                    else dp[i+2][j][k+1]=1;
                    
                    if(S[i+1]=='0') dp[i+2][j+1][k]=1;
                    else dp[i+2][j][k+1]=1;
                    
                    dp[i+1][j][k]=1;
                }
                
                if(j&&S[i]=='1') dp[i+1][j-1][k+1]=1;
                
                if(k&&S[i]=='0') dp[i+1][j+1][k-1]=1;
                
                if(j||k) dp[i+1][j][k]=1;
                
                if(j) dp[i][j-1][k]=1;
                
                if(k) dp[i][j][k-1]=1;
            }
        }
    }
    
    reverse(all(S));
    
    dp2[0][0][0]=1;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<=N;j++){
            for(int k=0;k<=N;k++){
                if(S[i]=='0'){
                    dp2[i][j][k+1]+=dp2[i][j][k];
                    dp2[i][j][k+1]%=mod;
                }else{
                    dp2[i][j+1][k]+=dp2[i][j][k];
                    dp2[i][j+1][k]%=mod;
                }
                dp2[i+1][j][k]+=dp2[i][j][k];
                dp2[i+1][j][k]%=mod;
            }
        }
    }
    
    ll ans=0;
    
    for(int i=0;i<=N;i++){
        for(int j=0;j<=N;j++){
            for(int k=0;k<=N;k++){
                if(dp[i][j][k]){
                    ans+=dp2[N-i][j][k];
                }
                ans%=mod;
            }
        }
    }
    
    cout<<ans<<endl;
}