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 MOD 998244353
using namespace std;
inline void Add(int &a,int b)
{a+=b;a>=MOD?a-=MOD:1;}
inline void Max(int &a,int b)
{a<b?a=b:1;}
const int Q=305;
int f[Q][Q][Q],ok[Q][Q][Q];
char s[Q];
int main()
{
    scanf("%s",s+1);
    int n=strlen(s+1);
    for(int i=0;i<=n;i++)
        (s[n]=='0'?f[n+1][0][i]:f[n+1][i][0])=1;
    for(int i=n;i;--i)
        for(int j=0;j<i;j++)
            for(int k=0;j+k<i;k++){
                f[i][j][k]=f[i+1][j][k];
                if(j&&s[i-1]=='1')Add(f[i][j][k],f[i][j-1][k]);
                if(k&&s[i-1]=='0')Add(f[i][j][k],f[i][j][k-1]);
            }
    for(int i=0;i<=n;i++)
        for(int j=0;j<=n;j++)
            fill(ok[i][j],ok[i][j]+n+1,(int)-1e9);
    ok[0][0][0]=ok[1][0][0]=0;
    for(int i=2;i<=n;i++)
        for(int j=0;j<=i;j++)
            for(int k=0;j+k<=i;k++){
                ok[i][j][k]=ok[i-1][j][k];
                if(j&&s[i]=='0')Max(ok[i][j][k],ok[i-1][j-1][k]-1);
                if(j&&min(s[i],s[i-1])=='0')Max(ok[i][j][k],ok[i-2][j-1][k]);
                if(k&&s[i]=='1')Max(ok[i][j][k],ok[i-1][j][k-1]-1);
                if(k&&max(s[i],s[i-1])=='1')Max(ok[i][j][k],ok[i-2][j][k-1]);
                Max(ok[i][j][k],ok[i-2][j][k]+1);
                if(ok[i][j][k]<0)ok[i][j][k]=-1e9;
            }
    int tmp=MOD-1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<i;j++)
            for(int k=0;j+k<i;k++)
                if(ok[i-1][j][k]>=0)
                    Add(tmp,f[i][j][k]);
    printf("%d\n",tmp);
    return 0;
}