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>
using namespace std;
typedef long long ll;
const int N=305,mod=998244353;
int n,p[2][N];
char s[N];
int dp[N][N][N];
bool f[N][N][N];
int main()
{
    scanf("%s",s+1);
    n=strlen(s+1);
    for(int i=1;i<=n;i++) p[0][i]=p[0][i-1]+(s[i]=='0'),p[1][i]=p[1][i-1]+(s[i]=='1');
    p[1][n+1]=p[1][n];p[0][n+1]=p[0][n];
    f[0][0][0]=true;
    for(int k=0;k<=n;k++)
        for(int i=0;i<=p[0][k];i++)
            for(int j=0;j<=p[1][k];j++)
    {
        if(!f[k][i][j]) continue;
        f[k+1][i][j]=true;
        if(i&&s[k+1]=='1')
            f[k+1][i-1][j+1]=true;
        if(j&&s[k+1]=='0')
            f[k+1][i+1][j-1]=true;
        if(k+2<=n&&(s[k+1]=='1'||s[k+2]=='1'))
            f[k+2][i][j+1]=true;
        if(k+2<=n&&(s[k+1]=='0'||s[k+2]=='0'))
            f[k+2][i+1][j]=true;
    }
    dp[n+1][0][0]=1;
    ll ans=0;
    for(int k=n+1;k>=1;k--)
        for(int i=0;i<=p[0][k];i++)
        for(int j=0;j<=p[1][k];j++)
    {
        if(dp[k][i][j]==0) continue;
        if(f[k-1][i][j])
            ans=(ans+dp[k][i][j])%mod;
        if(k>1)
        {
            dp[k-1][i][j]=(dp[k-1][i][j]+dp[k][i][j])%mod;
            if(s[k-1]=='1')
                dp[k][i+1][j]=(dp[k][i+1][j]+dp[k][i][j])%mod;
            else dp[k][i][j+1]=(dp[k][i][j+1]+dp[k][i][j])%mod;
        }
    }
    ans=(ans+mod-1)%mod;
    printf("%lld\n",ans);
}