#pragma comment(linker, "/STACK:512000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#ifdef AIM
#include <sys/resource.h>
#endif
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
  string s = FILENAME;
//    assert(!s.empty());
  freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif

#ifdef AIM
  const rlim_t kStackSize = 256 * 1024 * 1024;
  struct rlimit rl;
  int result;

  result = getrlimit(RLIMIT_STACK, &rl);
  if (result == 0)
  {
    if (rl.rlim_cur < kStackSize)
    {
      rl.rlim_cur = kStackSize;
      result = setrlimit(RLIMIT_STACK, &rl);
      if (result != 0)
      {
        fprintf(stderr, "setrlimit returned result = %d\n", result);
      }
    }
  }
#endif

  precalc();
  cout.precision(10);
  cout << fixed;
  //cin >> t;
  int testNum = 1;
  while (t--) {
      //cout << "Case #" << testNum++ << ": ";
      solve(true);
  }
  cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
  cout.flush();
  auto end = clock();

  usleep(10000);
  print_stats(end - start);
  usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 998244353;

void add(int& cur, int val) {
  cur += val;
  cur %= mod;
}

const int C = 310;
bool reachable[C][C][C];
int max_pref[C][C];
pair<int, int> in_air[C][C];

int fact[C], rev_fact[C];
int get_c(int n, int k) {
  return fact[n] * rev_fact[n - k] % mod * rev_fact[k] % mod;
}

void solve(__attribute__((unused)) bool read) {
  fact[0] = 1;
  for (int i = 1; i < C; ++i) {
    fact[i] = fact[i - 1] * i % mod;
  }
  for (int i = 0; i < C; ++i) {
    rev_fact[i] = binpow(fact[i], mod - 2, mod);
  }
  string s;
  //read = false;
  if (read) {
    cin >> s;
  } else {
    s = string(300, '0');
    for (int i = 0; i < s.length(); ++i) {
      if (rand() & 1) {
        s[i] = '1';
      }
    }
  }
  int n = (int)s.length();
  reachable[0][0][0] = true;
  for (int pref = 0; pref <= n; ++pref) {
    for (int a = C - 1; a >= 0; --a) { // 0s
      for (int b = C - 1; b >= 0; --b) { // 1s
        if (!reachable[pref][a][b]) {
          continue;
        }
        if (pref + 1 < n) {
          if (s[pref] == '0' || s[pref + 1] == '0') {
            reachable[pref + 2][a + 1][b] = true;
          }
          if (s[pref] == '1' || s[pref + 1] == '1') {
            reachable[pref + 2][a][b + 1] = true;
          }
        }
        if (a > 0 || b > 0) {
          reachable[pref + 1][a][b] = true;
          if (s[pref] == '0' && b > 0) {
            reachable[pref + 1][a + 1][b - 1] = true;
          }
          if (s[pref] == '1' && a > 0) {
            reachable[pref + 1][a - 1][b + 1] = true;
          }
        }
        if (a > 1) {
          reachable[pref][a - 2][b] = true;
        }
        if (b > 1) {
          reachable[pref][a][b - 2] = true;
        }
        if (a > 0 && b > 0) {
          reachable[pref][a - 1][b - 1] = true;
        }
      }
    }
  }
  for (int a = 0; a < C; ++a) {
    for (int b = 0; b < C; ++b) {
      max_pref[a][b] = -1;
    }
  }
  for (int pref = 0; pref <= n; ++pref) {
    int cnt[2] = {0, 0};
    for (int i = pref; i < n; ++i) {
      ++cnt[s[i] - '0'];
    }
    for (int a = 0; a < C; ++a) {
      for (int b = 0; b < C; ++b) {
        if (reachable[pref][a][b]) {
          max_pref[a + cnt[0]][b + cnt[1]] = pref;
          in_air[a + cnt[0]][b + cnt[1]] = {a, b};
        }
      }
    }
  }

  int res = 0;
  for (int a = 0; a < C; ++a) {
    for (int b = 0; b < C; ++b) {
      if (max_pref[a][b] == -1) {
        continue;
      }
      if (a + b == 0) {
        continue;
      }
      string cur = s.substr(max_pref[a][b], n - max_pref[a][b]);
      int cnt[2] = {0, 0};
      int places[2] = {0, 0};
      for (char c : cur) {
        ++cnt[c - '0'];
      }
      for (int i = 0; i < 2; ++i) {
        places[i] = cnt[1 - i];
      }
      //cout << a << " " << b << " " << places[0] << " " << places[1] << endl;
      int A = a - cnt[0], B = b - cnt[1];
      for (int x = 0; x <= A; ++x) {
        if (places[0] == 0 && x > 0) {
          break;
        }
        int x_mult = (places[0] == 0 ? 1 : get_c(x + places[0] - 1, x));
        for (int y = 0; y <= B; ++y) {
          if (places[1] == 0 && y > 0) {
            break;
          }
          int y_mult = (places[1] == 0 ? 1 : get_c(y + places[1] - 1, y));
          int cur_res = x_mult * y_mult % mod * get_c(A - x + B - y, A - x) % mod;
          //cout << "x: " << x << " y: " << y << " cur_res: " << cur_res << endl;
          add(res, cur_res);
        }
      }
    }
  }
  cout << res << "\n";

}
### Prompt

Develop a solution in cpp to the problem described below:

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

### Response

```cpp
#pragma comment(linker, "/STACK:512000000")
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
#ifdef AIM
#include <sys/resource.h>
#endif
using namespace std;

#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
void solve(__attribute__((unused)) bool);
void precalc();
clock_t start;
#define FILENAME ""

int main() {
#ifdef AIM
  string s = FILENAME;
//    assert(!s.empty());
  freopen("/home/alexandero/ClionProjects/cryptozoology/input.txt", "r", stdin);
  //freopen("/home/alexandero/ClionProjects/cryptozoology/output.txt", "w", stdout);
#else
//    freopen(FILENAME ".in", "r", stdin);
//    freopen(FILENAME ".out", "w", stdout);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
#endif
    start = clock();
    int t = 1;
#ifndef AIM
  cout.sync_with_stdio(0);
  cin.tie(0);
#endif

#ifdef AIM
  const rlim_t kStackSize = 256 * 1024 * 1024;
  struct rlimit rl;
  int result;

  result = getrlimit(RLIMIT_STACK, &rl);
  if (result == 0)
  {
    if (rl.rlim_cur < kStackSize)
    {
      rl.rlim_cur = kStackSize;
      result = setrlimit(RLIMIT_STACK, &rl);
      if (result != 0)
      {
        fprintf(stderr, "setrlimit returned result = %d\n", result);
      }
    }
  }
#endif

  precalc();
  cout.precision(10);
  cout << fixed;
  //cin >> t;
  int testNum = 1;
  while (t--) {
      //cout << "Case #" << testNum++ << ": ";
      solve(true);
  }
  cout.flush();
#ifdef AIM1
    while (true) {
      solve(false);
  }
#endif

#ifdef AIM
  cout.flush();
  auto end = clock();

  usleep(10000);
  print_stats(end - start);
  usleep(10000);
#endif

    return 0;
}

template<typename T>
T binpow(T q, T w, T mod) {
    if (!w)
        return 1 % mod;
    if (w & 1)
        return q * 1LL * binpow(q, w - 1, mod) % mod;
    return binpow(q * 1LL * q % mod, w / 2, mod);
}

template<typename T>
T gcd(T q, T w) {
    while (w) {
        q %= w;
        swap(q, w);
    }
    return q;
}
template<typename T>
T lcm(T q, T w) {
    return q / gcd(q, w) * w;
}

template <typename T>
void make_unique(vector<T>& a) {
    sort(all(a));
    a.erase(unique(all(a)), a.end());
}

template<typename T>
void relax_min(T& cur, T val) {
    cur = min(cur, val);
}

template<typename T>
void relax_max(T& cur, T val) {
    cur = max(cur, val);
}

void precalc() {
}

#define int li
const int mod = 998244353;

void add(int& cur, int val) {
  cur += val;
  cur %= mod;
}

const int C = 310;
bool reachable[C][C][C];
int max_pref[C][C];
pair<int, int> in_air[C][C];

int fact[C], rev_fact[C];
int get_c(int n, int k) {
  return fact[n] * rev_fact[n - k] % mod * rev_fact[k] % mod;
}

void solve(__attribute__((unused)) bool read) {
  fact[0] = 1;
  for (int i = 1; i < C; ++i) {
    fact[i] = fact[i - 1] * i % mod;
  }
  for (int i = 0; i < C; ++i) {
    rev_fact[i] = binpow(fact[i], mod - 2, mod);
  }
  string s;
  //read = false;
  if (read) {
    cin >> s;
  } else {
    s = string(300, '0');
    for (int i = 0; i < s.length(); ++i) {
      if (rand() & 1) {
        s[i] = '1';
      }
    }
  }
  int n = (int)s.length();
  reachable[0][0][0] = true;
  for (int pref = 0; pref <= n; ++pref) {
    for (int a = C - 1; a >= 0; --a) { // 0s
      for (int b = C - 1; b >= 0; --b) { // 1s
        if (!reachable[pref][a][b]) {
          continue;
        }
        if (pref + 1 < n) {
          if (s[pref] == '0' || s[pref + 1] == '0') {
            reachable[pref + 2][a + 1][b] = true;
          }
          if (s[pref] == '1' || s[pref + 1] == '1') {
            reachable[pref + 2][a][b + 1] = true;
          }
        }
        if (a > 0 || b > 0) {
          reachable[pref + 1][a][b] = true;
          if (s[pref] == '0' && b > 0) {
            reachable[pref + 1][a + 1][b - 1] = true;
          }
          if (s[pref] == '1' && a > 0) {
            reachable[pref + 1][a - 1][b + 1] = true;
          }
        }
        if (a > 1) {
          reachable[pref][a - 2][b] = true;
        }
        if (b > 1) {
          reachable[pref][a][b - 2] = true;
        }
        if (a > 0 && b > 0) {
          reachable[pref][a - 1][b - 1] = true;
        }
      }
    }
  }
  for (int a = 0; a < C; ++a) {
    for (int b = 0; b < C; ++b) {
      max_pref[a][b] = -1;
    }
  }
  for (int pref = 0; pref <= n; ++pref) {
    int cnt[2] = {0, 0};
    for (int i = pref; i < n; ++i) {
      ++cnt[s[i] - '0'];
    }
    for (int a = 0; a < C; ++a) {
      for (int b = 0; b < C; ++b) {
        if (reachable[pref][a][b]) {
          max_pref[a + cnt[0]][b + cnt[1]] = pref;
          in_air[a + cnt[0]][b + cnt[1]] = {a, b};
        }
      }
    }
  }

  int res = 0;
  for (int a = 0; a < C; ++a) {
    for (int b = 0; b < C; ++b) {
      if (max_pref[a][b] == -1) {
        continue;
      }
      if (a + b == 0) {
        continue;
      }
      string cur = s.substr(max_pref[a][b], n - max_pref[a][b]);
      int cnt[2] = {0, 0};
      int places[2] = {0, 0};
      for (char c : cur) {
        ++cnt[c - '0'];
      }
      for (int i = 0; i < 2; ++i) {
        places[i] = cnt[1 - i];
      }
      //cout << a << " " << b << " " << places[0] << " " << places[1] << endl;
      int A = a - cnt[0], B = b - cnt[1];
      for (int x = 0; x <= A; ++x) {
        if (places[0] == 0 && x > 0) {
          break;
        }
        int x_mult = (places[0] == 0 ? 1 : get_c(x + places[0] - 1, x));
        for (int y = 0; y <= B; ++y) {
          if (places[1] == 0 && y > 0) {
            break;
          }
          int y_mult = (places[1] == 0 ? 1 : get_c(y + places[1] - 1, y));
          int cur_res = x_mult * y_mult % mod * get_c(A - x + B - y, A - x) % mod;
          //cout << "x: " << x << " y: " << y << " cur_res: " << cur_res << endl;
          add(res, cur_res);
        }
      }
    }
  }
  cout << res << "\n";

}
```