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<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
int CC[310][310];
char p[310];
int M[310][310], w[310], vis[310][310], D[310][310][310], Mod = 998244353;
int n;
long long res;
void UDT(int i, int a, int b){
    if(M[i][a]<b)M[i][a]=b;
}
void Do(int L){
    int i, j, k;
    for(i=0;i<=n;i++){
        for(j=0;j<=n;j++){
            M[i][j]=-1;
        }
    }
    M[0][0]=0;
    for(i=0;i<L;i++){
        for(j=0;j<=L;j++){
            int a = j, b = M[i][j];
            if(b==-1)continue;
            UDT(i+1,a,b);
            if(i+2<=L){
                if(w[i+1]==0||w[i+2]==0)UDT(i+2, a+1,b);
                if(w[i+1]==1||w[i+2]==1)UDT(i+2, a,b+1);
            }
            if(w[i+1]==0 && b){
                UDT(i+1,a+1,b-1);
            }
            if(w[i+1]==1 && a){
                UDT(i+1,a-1,b+1);
            }
        }
    }
    int cc[2]={0};
    for(i=L+1;i<=n;i++){
        cc[w[i]]++;
    }
    for(i=0;i<=L;i++){
        for(j=0;j<=M[L][i];j++){
            if(!i&&!j)continue;
            int x = cc[0]+i,y = cc[1]+j;
            if(!vis[x][y]){
                vis[x][y]=1;
                for(k=n-L;k<=n;k++){
                    res+=D[x][y][k];
                }
            }
        }
    }
}
int main(){
    int i, j, k, l;
    scanf("%s",p);
    for(i=0;p[i];i++);
    n=i;
    for(i=1;i<=n;i++)w[i]=p[i-1]-'0';
    D[0][0][0]=1;
    for(i=0;i<=n;i++){
        for(j=0;i+j<=n;j++){
            for(k=0;k<=n;k++){
                if(!D[i][j][k])continue;
                int t = D[i][j][k];
                if(k+1<=n && w[n-(k+1)+1]==0){
                    D[i+1][j][k+1]=(D[i+1][j][k+1]+t)%Mod;
                }
                else{
                    D[i+1][j][k]=(D[i+1][j][k]+t)%Mod;
                }
                if(k+1<=n && w[n-(k+1)+1]==1){
                    D[i][j+1][k+1]=(D[i][j+1][k+1]+t)%Mod;
                }
                else{
                    D[i][j+1][k]=(D[i][j+1][k]+t)%Mod;
                }
            }
        }
    }
    for(i=n;i>=2;i--){
        Do(i);
    }
    res++;
    printf("%lld\n",res%Mod);
}