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 <algorithm>
#include <array>
#include <assert.h>
#include <bitset>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>

#include <istream>
#include <map>
#include <math.h>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

namespace asl
{
    
    template <typename T>
    std::vector<std::vector<std::vector<T>>> board3(int n = 0, int m = 0, int k = 0)
    {
        return std::vector<std::vector<std::vector<T>>>(n, std::vector<std::vector<T>>(m, std::vector<T>(k)));
    }

} 

namespace asl
{
    
    const int m1000000007 = 1000000007;
    
    const int m998244353 = 998244353;

    int MOD = m1000000007;

    void set_mod(int mod)
    {
        MOD = mod;
    }

    class Mint
    {
    public:
        int val;

        Mint(long long v = 0)
        {
            if (v >= 0)
            {
                if (v < MOD)
                    val = v;
                else
                    val = v % MOD;
            }
            else
            {
                if (v >= -MOD)
                {
                    val = v + MOD;
                }
                else
                {
                    v %= MOD;
                    if (v < 0)
                        v += MOD;
                    val = v;
                }
            }
        }

        Mint &operator+=(const Mint &other)
        {
            val += other.val;
            if (val >= MOD)
                val -= MOD;
            return *this;
        }

        friend std::ostream &operator<<(std::ostream &stream, const Mint &m)
        {
            return stream << m.val;
        }

    };
} 

#include <random>

#define endl '\n'

using namespace std;
using namespace asl;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    set_mod(m998244353);

    string s;
    cin >> s;

    int l = s.length();

    int digit_count[2] = {0, 0};
    for (auto x : s)
    {
        digit_count[x - '0']++;
    }

    auto dp = board3<Mint>(digit_count[0] + 1, digit_count[1] + 1, l + 1);
    dp[0][0][0] = 1;

    reverse(s.begin(), s.end());

    for (int z = 0; z <= digit_count[0]; ++z)
    {
        for (int o = 0; o <= digit_count[1]; ++o)
        {
            for (int i = 0; i <= l; ++i)
            {
                if (i && s[i - 1] == '0')
                    dp[z][o][i] += dp[z][o][i - 1];
                else if (z)
                    dp[z][o][i] += dp[z - 1][o][i];

                if (i && s[i - 1] == '1')
                    dp[z][o][i] += dp[z][o][i - 1];
                else if (o)
                    dp[z][o][i] += dp[z][o - 1][i];
            }
        }
    }

    reverse(s.begin(), s.end());

    Mint ans;

    auto reach = board3<bool>(digit_count[0] + 1, digit_count[1] + 1, l + 1);
    reach[0][0][0] = true;

    for (int i = 0; i <= l; ++i)
        for (int z = digit_count[0]; z >= 0; --z)
            for (int o = digit_count[1]; o >= 0; --o)
            {
                if (!reach[z][o][i])
                    continue;

                if (z + o > 1)
                {
                    if (z)
                        reach[z - 1][o][i] = true;

                    if (o)
                        reach[z][o - 1][i] = true;
                }

                if (i < l)
                {
                    if (z || o)
                        reach[z][o][i + 1] = true;

                    if (s[i] == '0' && o)
                        reach[z + 1][o - 1][i + 1] = true;

                    if (s[i] == '1' && z)
                        reach[z - 1][o + 1][i + 1] = true;
                }

                if (i + 1 < l)
                {
                    if (s[i] == '0' && s[i + 1] == '0')
                        reach[z + 1][o][i + 2] = true;

                    if (s[i] == '1' && s[i + 1] == '1')
                        reach[z][o + 1][i + 2] = true;

                    if (s[i] != s[i + 1])
                    {
                        reach[z + 1][o][i + 2] = true;
                        reach[z][o + 1][i + 2] = true;
                    }
                }
            }

    for (int i = 0; i <= l; ++i)
        for (int z = digit_count[0]; z >= 0; --z)
            for (int o = digit_count[1]; o >= 0; --o)
            {
                if (!reach[z][o][i])
                    continue;

                if (i < l)
                {
                    if (s[i] == '0' && z + 1 <= digit_count[0])
                        if (reach[z + 1][o][i + 1])
                            continue;

                    if (s[i] == '1' && o + 1 <= digit_count[1])
                        if (reach[z][o + 1][i + 1])
                            continue;
                }

                ans += dp[z][o][l - i];
            }

    cout << ans << endl;

    return 0;
}