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"
#include<vector>
#include<iostream>
#include<queue>
#include<algorithm>
#include<map>
#include<set>
#include<iomanip>
#include<assert.h>
#include<unordered_map>
#include<unordered_set>
#include<string>
#include<stack>
#include<complex>
#include<memory>

#pragma warning(disable:4996)
using namespace std;
using ld = long double;
template<class T>
using Table = vector<vector<T>>;
const ld eps=1e-9;
using Graph=vector<vector<int>>;
	
#define WHATS(var)cout<<__LINE__<<' '<<#var<<"="<<var<<endl;
	
template<class S, class T> ostream& operator <<(ostream &os, const pair<S, T> v){
	os << "( " << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<T> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<vector<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const vector<set<T>> &v){
	for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
template<class T> ostream& operator <<(ostream &os, const set<T> &v){
	int i=0;
	for(auto it:v){
		if(i > 0){os << ' ';}
		os << it;
		i++;
	} 
	return os;
}
//1. maskの部分集合を列挙する
	// 	a. i==0を評価しない
	// 	for(int i=mask; i>0; i=(i-1)&mask) {
	// 	}

	// b. i==0を評価する
	// 	for(int i=mask; i>=0; i--) {
	// 		i&=mask;
	// 	}
// 2. maskを含む集合を列挙する

// 少し目的は変わりますが同じようなやり方でできる処理が、maskを含む集合の列挙です。

// 	for(int i=mask; i<(1<<n); i=(i+1)|mask) {
// 	}

	
using ll = long long int;

int say(vector<int>v){
    cout<<v.size();
    for(auto x:v)cout<<' '<<x+1;
    cout<<endl;

    int a;cin>>a;
    a--;
    return a;
}
///02020
//02110
//02200
//03010
//03100
//04000
//20020
//11020
//11110
//11200
//12010
//12100
//13000
//22020
const ll mod=998244353;
vector<vector<ll>>calc(vector<vector<ll>>v,bool flag=false){
    if(!flag){
        vector<vector<ll>>sums(v.size(),vector<ll>(v[0].size()+1));
        for(int y=0;y<v.size();++y){
            for(int x=0;x<v[0].size();++x){
                sums[y][x+1]+=v[y][x];
                sums[y][x+1]+=sums[y][x];

                sums[y][x+1]%=mod;
            }
        }
        return sums;
    }else{
        vector<vector<ll>>sums(v.size()+1,vector<ll>(v[0].size()+1));
        for(int y=0;y<v.size();++y){
            for(int x=v[0].size()-1;x>=0;--x){
                sums[y+1][x]+=v[y][x];
                sums[y+1][x]+=sums[y][x+1];

                sums[y+1][x]%=mod;
            }
        }
        return sums;
    }
}
int main() {
	ios::sync_with_stdio(false);
    cin.tie();
    string st;cin>>st;
    const int N=st.size();
    vector<vector<vector<ll>>>dp(N+1,vector<vector<ll>>(N+1,vector<ll>(N+1)));
    dp[0][N][0]=1ll;

    for(int len=1;len<=N;++len){
        for(int x=N;x>=N-len+1;--x){
            
            int need_sum=(len-1)-(N-x);
            // WHATS(len)
            // WHATS(x)
            // WHATS(need_sum)
            for(int one_need=0;one_need<=need_sum;++one_need){
                
                

                int zero_need=need_sum-one_need;
                
                if(x>=0){
                    if(st[x-1]=='1'){
                        dp[len][x][one_need]+=dp[len-1][x][one_need];
                        dp[len][x-1][one_need]+=dp[len-1][x][one_need];
                    }else{
                        
                        dp[len][x][one_need+1]+=dp[len-1][x][one_need];
                        dp[len][x-1][one_need]+=dp[len-1][x][one_need];
                    }
                }
               
            }
        }
        for(int x=0;x<=N;++x){
            for(int y=0;y<=N;++y){
                dp[len][x][y]%=mod;
            }
        }
    }
    //WHATS(dp[1])
    //WHATS(dp[2])
    ll answer=0;
    vector<int>one_sums(N+1);
    vector<int>zero_sums(N+1);
    for(int i=1;i<=N;++i){
        if((i>=2)){
            if(st[i-1]=='1'||st[i-2]=='1'){
                one_sums[i]=max(one_sums[i],one_sums[i-2]+1);
                
            }else{
                one_sums[i]=max(one_sums[i],one_sums[i-2]);

            }

            if(st[i-1]=='0'||st[i-2]=='0'){
                zero_sums[i]=max(zero_sums[i],zero_sums[i-2]+1);
            }else{
                zero_sums[i]=max(zero_sums[i],zero_sums[i-2]);

            }
        }
        {//111001110011100111 1:8 0:3
            one_sums[i]=max(one_sums[i],one_sums[i-1]);
            zero_sums[i]=max(zero_sums[i],zero_sums[i-1]);
        }
    }

    vector<vector<vector<int>>>oks(N+1,vector<vector<int>>(N+2,vector<int>(N+2)));
    oks[0][0][0]=true;
    for(int x=0;x<N;++x){
        for(int z_cnt=0;z_cnt<=N;++z_cnt){
            for(int o_cnt=0;o_cnt<=N;++o_cnt){
                if(oks[x][z_cnt][o_cnt]){
                    oks[x+1][z_cnt][o_cnt]=true;
                    if(x<N-1){
                        if(st[x]=='0'||st[x+1]=='0'){
                            oks[x+2][z_cnt+1][o_cnt]=true;
                        }
                        
                        if(st[x]=='1'||st[x+1]=='1'){
                            oks[x+2][z_cnt][o_cnt+1]=true;
                        }
                        
                    }
                    {
                        if(st[x]=='1'){
                            if(z_cnt){
                                oks[x+1][z_cnt-1][o_cnt+1]=true;
                            }
                            
                        }
                        if(st[x]=='0'){
                            if(o_cnt){
                                oks[x+1][z_cnt+1][o_cnt-1]=true;
                            }
                        }
                    }
                }
            }
        }
    }
    // WHATS(oks[3])
    // WHATS(oks[4])
    // WHATS(oks[5])
    // WHATS(oks[6])
    for(int i=1;i<=N;++i){
        int len=i;
        for(int j=N;j>=N-len;--j){
            int x=j;
            int need_sum=(len)-(N-x);

            for(int k=0;k<=N;++k){
                int one_need=k;
                int zero_need=need_sum-one_need;

                
                if(zero_need<0)continue;

                int one_sum=one_sums[x];
                int zero_sum=zero_sums[x];
                //int carry_time=N-len;
                 //if(one_need<=one_sum&&zero_need<=zero_sum&&(x)>=2*(one_need+zero_need)){
                if(oks[x][zero_need][one_need]){    
                        
                    if(dp[i][j][k]){
                        //  WHATS(len)
                        //  WHATS(x)
                        //  WHATS(one_need)
                        // WHATS(zero_need)
                        // WHATS(dp[i][j][k])
                        answer+=dp[i][j][k];
                    }
                }
            }
        }
    }
    answer+=mod;
    cout<<answer%mod<<endl;

    // set<string>aset;
    // queue<string>que;
    // que.emplace(st);
    // aset.emplace(st);
    
    // while(!que.empty()){
    //     string q(que.front());
    //     que.pop();
    //     aset.emplace(q);
    //     if(q.size()>=2){

    //         char ch='0';
    //         for(char ch='0';ch<='1';++ch){
    //              if(q[0]==ch||q[1]==ch){
    //                 for(int x=2;x<=q.size();++x){
    //                     string l=q.substr(2,x-2);
    //                     string r=q.substr(x);

    //                     string kk=l+ch+r;
    //                     if(aset.find(kk)==aset.end()){
    //                         que.emplace(l+ch+r);
    //                         aset.emplace(kk);
    //                     }
    //                 }
    //             }
    //         }
           
    //     }
    // }
    // WHATS(aset.size())
    return 0;
}