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;
#define finish(x) return cout << x << endl, 0
#define ll long long
 
const int N = 305;
 
int n, c[N][N][N], dp[N][N][N], f[N][N], mod = 998244353;
string s;
 
void go(int idx, int z, int o){
    if(c[idx][z][o]) return;
    c[idx][z][o] = 1;
    if(z >= 2) go(idx, z - 1, o);
    if(o >= 2) go(idx, z, o - 1);
    if(o >= 1 && z >= 1){
        go(idx, z - 1, o);
        go(idx, z, o - 1);
    }
    if(idx < n && s[idx] == '1' && z){
        go(idx + 1, z, o);
        go(idx + 1, z - 1, o + 1);
    }
    if(idx < n && s[idx] == '0' && o){
        go(idx + 1, z, o);
        go(idx + 1, z + 1, o - 1);
    }
    if(idx < n && s[idx] == '0' && z){
        go(idx + 1, z, o);
    }
    if(idx < n && s[idx] == '1' && o){
        go(idx + 1, z, o);
    }
    if(idx + 1 < n && (s[idx] == '0' || s[idx + 1] == '0')){
        go(idx + 2, z + 1, o);
    }
    if(idx + 1 < n && (s[idx] == '1' || s[idx + 1] == '1')){
        go(idx + 2, z, o + 1);
    }
}
int solve(int idx, int z, int o){
    if(idx == n && z == 0 && o == 0) return 1;
    int &ret = dp[idx][z][o];
    if(ret != -1) return ret;
    ret = 0;
    // 0
    if(s[idx] == '0') ret += solve(idx + 1, z, o);
    else if(z) ret += solve(idx, z - 1, o);
    if(ret >= mod) ret -= mod;
    // 1
    if(s[idx] == '1') ret += solve(idx + 1, z, o);
    else if(o) ret += solve(idx, z, o - 1);
    if(ret >= mod) ret -= mod;
    return ret;
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    memset(dp, -1, sizeof dp);
    cin >> s;
    n = s.size();
    go(0, 0, 0);
    vector <int> suff(n + 1);
    for(int i = n - 1 ; i >= 0 ; i--){
        suff[i] = suff[i + 1];
        suff[i] += s[i] - '0';
    }
    memset(f, -1, sizeof f);
    for(int i = 0 ; i <= n ; i++){
        for(int z = 0 ; z <= n ; z++){
            for(int o = 0 ; o <= n ; o++){
                if(c[i][z][o]){
                    int zeros = n - i - suff[i] + z;
                    int ones = suff[i] + o;
                    f[zeros][ones] = i;
                }
            }
        }
    }
    int ans = 0;
    for(int z = 0 ; z <= n ; z++){
        for(int o = 0 ; o <= n ; o++){
            int i = f[z][o];
            if(i == -1) continue;
            int zeros = z - (n - i - suff[i]);
            int ones = o - suff[i];
            ans += solve(i, zeros, ones);
            if(ans >= mod) ans -= mod;
        }
    }
    cout << ans << endl;
}