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<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
constexpr int inf=1e9+7;
constexpr ll longinf=1LL<<60 ;
constexpr ll mod=998244353 ;


ll dp[333][333][333], dp2[333][333][333], used[666][666];
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin>>s;
    int n=s.size();
    string t(s.rbegin(),s.rend());
    dp[0][0][0]=1;
    rep(i,n+1)rep(j,301)rep(k,301){
        if(i==0&&j==0&&k==0)continue;
        if(i==0){
            if(j>0)dp[i][j][k]+=dp[i][j-1][k];
            if(k>0)dp[i][j][k]+=dp[i][j][k-1];
        }
        if(i>0 && t[i-1]=='0'){
            dp[i][j][k]+=dp[i-1][j][k];
            if(k>0)dp[i][j][k]+=dp[i][j][k-1];
        }
        if(i>0 && t[i-1]=='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;
    }
    dp2[0][0][0]=1;
    rep(i,n+1)for(int j=300;j>=0;--j)for(int k=300;k>=0;--k){
        if(j>=2)dp2[i][j-2][k]|=dp2[i][j][k];
        if(k>=2)dp2[i][j][k-2]|=dp2[i][j][k];
        if(j>=1 && k>=1)dp2[i][j-1][k-1]|=dp2[i][j][k];
        if(i<n && s[i]=='0'){
            if(j>0||k>0)dp2[i+1][j][k]|=dp2[i][j][k];
            if(k>0)dp2[i+1][j+1][k-1]|=dp2[i][j][k];
        }
        if(i<n && s[i]=='1'){
            if(j>0)dp2[i+1][j-1][k+1]|=dp2[i][j][k];
            if(j>0||k>0)dp2[i+1][j][k]|=dp2[i][j][k];
        }
        if(i+1<n){
            if(s[i]=='0'||s[i+1]=='0')dp2[i+2][j+1][k]|=dp2[i][j][k];
            if(s[i]=='1'||s[i+1]=='1')dp2[i+2][j][k+1]|=dp2[i][j][k];
        }
    }
    ll ans=0;
    int z=0, o=0;
    used[0][0]=1;
    rep(i,n+1){
        if(i!=0){
            if(s[n-i]=='0')z++;
            else o++;
        }
        rep(j,n+1)rep(k,n+1){
            if(dp2[n-i][j][k] && !used[z+j][o+k]){
                ans+=dp[i][j][k];
                used[z+j][o+k]=1;
            }
        }
    }
    cout<<ans%mod<<endl;
    return 0;
}