#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 600 + 7;
const int M = 998244353;

int mul(int a, int b) {
  return (a * (ll) b) % M;
}

int sum(int a, int b) {
  int c = (a + b) % M;
  if (c >= M) c -= M;
  if (c < 0) c += M;
  return c;
}

void add(int &a, int b) {
  a = sum(a ,b);
}

bool dp[N][N][N];
int vals[N][N][N];

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  int n = (int) s.size();
  dp[0][0][0] = true;
  for (int i = 0; i <= n; i++) {
    for (int x = n; x >= 0; x--) {
      for (int y = n; y >= 0; y--) {
        if (!dp[i][x][y]) continue;
        if (x + y >= 2) {
          if (x)
            dp[i][x - 1][y] = true;
          if (y)
            dp[i][x][y - 1] = true;
        }
        if (x + y >= 1) {
          dp[i + 1][x][y] = true;
        }
        if (x && i < n) {
          if (s[i] == '0') {
            dp[i + 1][x][y] = true;
          } else {
            dp[i + 1][x - 1][y + 1] = true;
          }
        }
        if (y && i < n) {
          if (s[i] == '0') {
            dp[i + 1][x + 1][y - 1] = true;
          } else {
            dp[i + 1][x][y] = true;
          }
        }
        if (i + 1 < n) {
          if (s[i] == s[i + 1]) {
            if (s[i] == '0') {
              dp[i + 2][x + 1][y] = true;
            } else {
              dp[i + 2][x][y + 1] = true;
            }
          } else {
            dp[i + 2][x + 1][y] = true;
            dp[i + 2][x][y + 1] = true;
          }
        }
      }
    }
  }
  vals[n][0][0] = 1;
  for (int i = n; i >= 0; i--) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (x + 1 <= n) {
          if (!i || s[i - 1] != '0')
            add(vals[i][x + 1][y], vals[i][x][y]);
          else
            add(vals[i - 1][x + 1][y], vals[i][x][y]);
        }
        if (y + 1 <= n) {
          if (!i || s[i - 1] != '1')
            add(vals[i][x][y + 1], vals[i][x][y]);
          else
            add(vals[i - 1][x][y + 1], vals[i][x][y]);
        }
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (i) add(vals[i][x][y], vals[i - 1][x][y]);
      }
    }
  }
  vector <int> pa(n + 1), pb(n + 1);
  int a = 0, b = 0;
  for (int i = n; i >= 0; i--) {
    if (i < n && s[i] == '0') a++;
    if (i < n && s[i] == '1') b++;
    pa[i] = a, pb[i] = b;
  }
  auto cost = [&] (int i, int a, int b) {
    a += pa[i], b += pb[i];
    int sum = vals[i][a][b];
    return sum;
  };
  int ans = 0;
  for (int i = n; i >= 0; i--) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (dp[i][x][y]) {
          int cur = 0;
          add(cur, cost(i, x, y));
          if (i) {
            if (s[i - 1] == '0' && x && dp[i - 1][x - 1][y]) {
              add(cur, -cost(i - 1, x - 1, y));
            }
            if (s[i - 1] == '1' && y && dp[i - 1][x][y - 1]) {
              add(cur, -cost(i - 1, x, y - 1));
            }
          }
          add(ans, cur);
        }
      }
    }
  }
  cout << ans % M << endl;
}

### Prompt

Please create a solution in cpp to the following 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

### Response

```cpp
#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

typedef long long ll;

#ifdef iq
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif

const int N = 600 + 7;
const int M = 998244353;

int mul(int a, int b) {
  return (a * (ll) b) % M;
}

int sum(int a, int b) {
  int c = (a + b) % M;
  if (c >= M) c -= M;
  if (c < 0) c += M;
  return c;
}

void add(int &a, int b) {
  a = sum(a ,b);
}

bool dp[N][N][N];
int vals[N][N][N];

int main() {
#ifdef iq
  freopen("a.in", "r", stdin);
#endif
  ios::sync_with_stdio(0);
  cin.tie(0);
  string s;
  cin >> s;
  int n = (int) s.size();
  dp[0][0][0] = true;
  for (int i = 0; i <= n; i++) {
    for (int x = n; x >= 0; x--) {
      for (int y = n; y >= 0; y--) {
        if (!dp[i][x][y]) continue;
        if (x + y >= 2) {
          if (x)
            dp[i][x - 1][y] = true;
          if (y)
            dp[i][x][y - 1] = true;
        }
        if (x + y >= 1) {
          dp[i + 1][x][y] = true;
        }
        if (x && i < n) {
          if (s[i] == '0') {
            dp[i + 1][x][y] = true;
          } else {
            dp[i + 1][x - 1][y + 1] = true;
          }
        }
        if (y && i < n) {
          if (s[i] == '0') {
            dp[i + 1][x + 1][y - 1] = true;
          } else {
            dp[i + 1][x][y] = true;
          }
        }
        if (i + 1 < n) {
          if (s[i] == s[i + 1]) {
            if (s[i] == '0') {
              dp[i + 2][x + 1][y] = true;
            } else {
              dp[i + 2][x][y + 1] = true;
            }
          } else {
            dp[i + 2][x + 1][y] = true;
            dp[i + 2][x][y + 1] = true;
          }
        }
      }
    }
  }
  vals[n][0][0] = 1;
  for (int i = n; i >= 0; i--) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (x + 1 <= n) {
          if (!i || s[i - 1] != '0')
            add(vals[i][x + 1][y], vals[i][x][y]);
          else
            add(vals[i - 1][x + 1][y], vals[i][x][y]);
        }
        if (y + 1 <= n) {
          if (!i || s[i - 1] != '1')
            add(vals[i][x][y + 1], vals[i][x][y]);
          else
            add(vals[i - 1][x][y + 1], vals[i][x][y]);
        }
      }
    }
  }
  for (int i = 0; i <= n; i++) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (i) add(vals[i][x][y], vals[i - 1][x][y]);
      }
    }
  }
  vector <int> pa(n + 1), pb(n + 1);
  int a = 0, b = 0;
  for (int i = n; i >= 0; i--) {
    if (i < n && s[i] == '0') a++;
    if (i < n && s[i] == '1') b++;
    pa[i] = a, pb[i] = b;
  }
  auto cost = [&] (int i, int a, int b) {
    a += pa[i], b += pb[i];
    int sum = vals[i][a][b];
    return sum;
  };
  int ans = 0;
  for (int i = n; i >= 0; i--) {
    for (int x = 0; x <= n; x++) {
      for (int y = 0; y <= n; y++) {
        if (dp[i][x][y]) {
          int cur = 0;
          add(cur, cost(i, x, y));
          if (i) {
            if (s[i - 1] == '0' && x && dp[i - 1][x - 1][y]) {
              add(cur, -cost(i - 1, x - 1, y));
            }
            if (s[i - 1] == '1' && y && dp[i - 1][x][y - 1]) {
              add(cur, -cost(i - 1, x, y - 1));
            }
          }
          add(ans, cur);
        }
      }
    }
  }
  cout << ans % M << endl;
}

```