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>
#define F first
#define S second
#define pb push_back
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pi;
const int maxn=305;
const int M=998244353;
int n,ans;
char s[maxn];
bool f[maxn][maxn][maxn],g[maxn][maxn][maxn];
int dp[maxn][maxn][maxn];

void add(int &x,int y){
    x+=y; if(x>=M) x-=M;
}

int main(){
    scanf("%s",s+1); n=strlen(s+1);
    f[0][0][0]=1;
    for (int i=0;i<=n-1;i++)
    for (int j=0;j<=n;j++)
    for (int k=0;k<=n;k++) if (f[i][j][k]){
        // x:0   y:1
        int x=k,y=j-i-k;
        g[n-j][x][y]=1;
        if (i==n-1) continue;
        if (x>=2) f[i+1][j][k-1]=1;
        if (x>=1&&y>=1) f[i+1][j][k-1]=1,f[i+1][j][k]=1;
        if (y>=2) f[i+1][j][k]=1;
        if (j<n){
            if (s[j+1]=='0'){
                if (x>=1) f[i+1][j+1][k]=1;
                if (y>=1) f[i+1][j+1][k]=f[i+1][j+1][k+1]=1;
            } else {
                if (x>=1) f[i+1][j+1][k-1]=f[i+1][j+1][k]=1;
                if (y>=1) f[i+1][j+1][k]=1;
            }
        }
        if (j<n-1){
            int zeros=(s[j+1]=='0')+(s[j+2]=='0');
            if (zeros==2){
                f[i+1][j+2][k+1]=1;
            } else if (zeros==1){
                f[i+1][j+2][k]=f[i+1][j+2][k+1]=1;
            } else {
                f[i+1][j+2][k]=1;
            }
        }
    }
    for (int i=1;i<=n;i++)
    for (int j=0;j<=n;j++)
    for (int k=0;k<=n;k++){
        if (s[n-i+1]=='0') g[i][j][k]|=g[i-1][j+1][k];
        else g[i][j][k]|=g[i-1][j][k+1];
    }
    dp[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[n-i]=='0'){
            add(dp[i][j][k+1],dp[i][j][k]);
        } else if (s[n-i]=='1') {
            add(dp[i][j+1][k],dp[i][j][k]);
        }
        add(dp[i+1][j][k],dp[i][j][k]);
        if (g[i][j][k]) {
            if (i+j+k) add(ans,dp[i][j][k]);
            //cout<<i<<' '<<j<<' '<<k<<' '<<dp[i][j][k]<<endl;
        }
    }
    cout << ans << endl;
    return 0;
}