#include <bits/stdc++.h>
using namespace std;
typedef bool boolean;

template <typename T>
boolean vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
boolean vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}

template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename ...K>
T smax(T a, const K &...args) {
  return max(a, smax(args...));
}

template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename ...K>
T smin(T a, const K &...args) {
  return min(a, smin(args...));
}

// debugging lib

#define VN(x) #x
#define Vmsg(x) VN(x) << " = " << (x)
#define printv(x) cerr << VN(x) << " = " << (x);
#define debug(...) fprintf(stderr, __VA_ARGS__);

template <typename A, typename B>
ostream& operator << (ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
  boolean isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}

#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define ll long long
#define ull unsigned long long

const int inf = (signed) (~0u >> 2);
const ll llf = (signed ll) (~0ull >> 2);

#define pb push_back
#define eb emplace_back
#define fi first
#define sc second

template <typename T>
int vsize(vector<T>& x) {
  return (signed) x.size(); 
}

template <typename T>
int discrete(T* a, int* b, int n) {
  vector<T> v(a + 1, a + n + 1);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++) b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
  return v.size();
}

mt19937 rng (time(NULL));

int randint(int l, int r) {
  return rng() % (r - l + 1) + l;
}


#define ll long long

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}

int inv(int a, int n) {
  int x, y;
  exgcd(a, n, x, y);
  return (x < 0) ? (x + n) : (x);
}

const int Mod = 998244353;

template <const int Mod = :: Mod>
class Z {
  public:
    int v;

    Z() : v(0) {	}
    Z(int x) : v(x){	}
    Z(ll x) : v(x % Mod) {	}

    friend Z operator + (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
    }
    friend Z operator - (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
    }
    friend Z operator * (const Z& a, const Z& b) {
      return Z(a.v * 1ll * b.v);
    }
    friend Z operator ~(const Z& a) {
      return inv(a.v, Mod);
    }
    friend Z operator - (const Z& a) {
      return Z(0) - a;
    }
    Z& operator += (Z b) {
      return *this = *this + b;
    }
    Z& operator -= (Z b) {
      return *this = *this - b;
    }
    Z& operator *= (Z b) {
      return *this = *this * b;
    }
    friend boolean operator == (const Z& a, const Z& b) {
      return a.v == b.v;
    } 
};

Z<> qpow(Z<> a, int p) {
  Z<> rt = Z<>(1), pa = a;
  for ( ; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}

typedef Z<> Zi;

const int N = 305;

int n;
char s[N];
bool f[N][N][N];
Zi g[N][N][N];

set<string> S;

void check(string t) {
  int len = t.length();
  int p = n, x = 0, y = 0;
  for (int i = len; i--; ) {
    if (t[i] == s[p]) {
      p--;
    } else {
      (t[i] == '0' ? x : y)++;
    }
  }
  if (!f[p][x][y]) {
    cerr << t << '\n';
  }
}

void dfs(string s) {
  if (S.count(s)) return;
  S.insert(s);
  check(s);
  if (s.length() < 2u)
    return;
  string t = s;
  t.erase(t.begin());
  t.erase(t.begin());
  char x = s[0], y = s[1];
  for (int i = 0; i < (signed) t.size(); i++) {
    string nt = t;
    nt.insert(nt.begin() + i, x);
    dfs(nt);
    nt = t;
    nt.insert(nt.begin() + i, y);
    dfs(nt);
  }
  string nt = t;
  nt += x;
  dfs(nt);
  nt = t;
  nt += y; 
  dfs(nt);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> (s + 1);
  n = strlen(s + 1);
  f[0][0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = n; ~j; j--) {
      for (int k = n; ~k; k--) {
        if (i == n && !j && !k) continue;
        f[i][j][k] |= f[i - 1][j][k];
        if (s[i] == '0') f[i][j][k] |= f[i][j][k + 1];
        if (s[i] == '1') f[i][j][k] |= f[i][j + 1][k];
      } 
    }
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k <= n; k++) {
        if (i > 1) {
          if ((s[i] == '0' || s[i - 1] == '0') && j) {
            f[i][j][k] |= f[i - 2][j - 1][k];
          }
          if ((s[i] == '0' && s[i - 1] == '0') && j) {
            f[i][j][k] |= f[i - 1][j - 1][k + 1];
          }
          if ((s[i] == '1' || s[i - 1] == '1') && k) {
            f[i][j][k] |= f[i - 2][j][k - 1];
          }
          if ((s[i] == '1' && s[i - 1] == '1') && k) {
            f[i][j][k] |= f[i - 1][j + 1][k - 1];
          }
        }
      }
    }
  }
  g[n + 1][0][0] = 1;
  for (int i = n + 1; i > 1; i--) {
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k <= n; k++) {
        Zi v = g[i][j][k];
        if (!v.v)
          continue;
        g[i - 1][j][k] += v;
        if (s[i - 1] == '0')
          g[i][j][k + 1] += v;
        if (s[i - 1] == '1')
          g[i][j + 1][k] += v;
      }
    }
  }
  Zi ans = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k <= i; k++) {
        if (f[i][j][k]) {
          ans += g[i + 1][j][k];
//          cerr << g[i + 1][j][k].v << " " << i + 1 << " " << j << " "<< k << '\n';
        }
      }
    }
  }
//  dfs(string(s + 1));
  printf("%d\n", ans.v);
  return 0;
}

### Prompt

Create a solution in CPP for 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 <bits/stdc++.h>
using namespace std;
typedef bool boolean;

template <typename T>
boolean vmin(T& a, T b) {
  return (a > b) ? (a = b, true) : (false);
}
template <typename T>
boolean vmax(T& a, T b) {
  return (a < b) ? (a = b, true) : (false);
}

template <typename T>
T smax(T x) {
  return x;
}
template <typename T, typename ...K>
T smax(T a, const K &...args) {
  return max(a, smax(args...));
}

template <typename T>
T smin(T x) {
  return x;
}
template <typename T, typename ...K>
T smin(T a, const K &...args) {
  return min(a, smin(args...));
}

// debugging lib

#define VN(x) #x
#define Vmsg(x) VN(x) << " = " << (x)
#define printv(x) cerr << VN(x) << " = " << (x);
#define debug(...) fprintf(stderr, __VA_ARGS__);

template <typename A, typename B>
ostream& operator << (ostream& os, const pair<A, B>& z) {
  os << "(" << z.first << ", " << z.second << ')';
  return os;
}
template <typename T>
ostream& operator << (ostream& os, const vector<T>& a) {
  boolean isfirst = true;
  os << "{";
  for (auto z : a) {
    if (!isfirst) {
      os << ", ";
    }
    os << z;
    isfirst = false;
  }
  os << '}';
  return os;
}

#define pii pair<int, int>
#define pil pair<int, ll>
#define pli pair<ll, int>
#define ll long long
#define ull unsigned long long

const int inf = (signed) (~0u >> 2);
const ll llf = (signed ll) (~0ull >> 2);

#define pb push_back
#define eb emplace_back
#define fi first
#define sc second

template <typename T>
int vsize(vector<T>& x) {
  return (signed) x.size(); 
}

template <typename T>
int discrete(T* a, int* b, int n) {
  vector<T> v(a + 1, a + n + 1);
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
  for (int i = 1; i <= n; i++) b[i] = lower_bound(v.begin(), v.end(), a[i]) - v.begin() + 1;
  return v.size();
}

mt19937 rng (time(NULL));

int randint(int l, int r) {
  return rng() % (r - l + 1) + l;
}


#define ll long long

void exgcd(int a, int b, int& x, int& y) {
  if (!b) {
    x = 1, y = 0;
  } else {
    exgcd(b, a % b, y, x);
    y -= (a / b) * x;
  }
}

int inv(int a, int n) {
  int x, y;
  exgcd(a, n, x, y);
  return (x < 0) ? (x + n) : (x);
}

const int Mod = 998244353;

template <const int Mod = :: Mod>
class Z {
  public:
    int v;

    Z() : v(0) {	}
    Z(int x) : v(x){	}
    Z(ll x) : v(x % Mod) {	}

    friend Z operator + (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v + b.v) >= Mod) ? (x - Mod) : (x));
    }
    friend Z operator - (const Z& a, const Z& b) {
      int x;
      return Z(((x = a.v - b.v) < 0) ? (x + Mod) : (x));
    }
    friend Z operator * (const Z& a, const Z& b) {
      return Z(a.v * 1ll * b.v);
    }
    friend Z operator ~(const Z& a) {
      return inv(a.v, Mod);
    }
    friend Z operator - (const Z& a) {
      return Z(0) - a;
    }
    Z& operator += (Z b) {
      return *this = *this + b;
    }
    Z& operator -= (Z b) {
      return *this = *this - b;
    }
    Z& operator *= (Z b) {
      return *this = *this * b;
    }
    friend boolean operator == (const Z& a, const Z& b) {
      return a.v == b.v;
    } 
};

Z<> qpow(Z<> a, int p) {
  Z<> rt = Z<>(1), pa = a;
  for ( ; p; p >>= 1, pa = pa * pa) {
    if (p & 1) {
      rt = rt * pa;
    }
  }
  return rt;
}

typedef Z<> Zi;

const int N = 305;

int n;
char s[N];
bool f[N][N][N];
Zi g[N][N][N];

set<string> S;

void check(string t) {
  int len = t.length();
  int p = n, x = 0, y = 0;
  for (int i = len; i--; ) {
    if (t[i] == s[p]) {
      p--;
    } else {
      (t[i] == '0' ? x : y)++;
    }
  }
  if (!f[p][x][y]) {
    cerr << t << '\n';
  }
}

void dfs(string s) {
  if (S.count(s)) return;
  S.insert(s);
  check(s);
  if (s.length() < 2u)
    return;
  string t = s;
  t.erase(t.begin());
  t.erase(t.begin());
  char x = s[0], y = s[1];
  for (int i = 0; i < (signed) t.size(); i++) {
    string nt = t;
    nt.insert(nt.begin() + i, x);
    dfs(nt);
    nt = t;
    nt.insert(nt.begin() + i, y);
    dfs(nt);
  }
  string nt = t;
  nt += x;
  dfs(nt);
  nt = t;
  nt += y; 
  dfs(nt);
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> (s + 1);
  n = strlen(s + 1);
  f[0][0][0] = true;
  for (int i = 1; i <= n; i++) {
    for (int j = n; ~j; j--) {
      for (int k = n; ~k; k--) {
        if (i == n && !j && !k) continue;
        f[i][j][k] |= f[i - 1][j][k];
        if (s[i] == '0') f[i][j][k] |= f[i][j][k + 1];
        if (s[i] == '1') f[i][j][k] |= f[i][j + 1][k];
      } 
    }
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k <= n; k++) {
        if (i > 1) {
          if ((s[i] == '0' || s[i - 1] == '0') && j) {
            f[i][j][k] |= f[i - 2][j - 1][k];
          }
          if ((s[i] == '0' && s[i - 1] == '0') && j) {
            f[i][j][k] |= f[i - 1][j - 1][k + 1];
          }
          if ((s[i] == '1' || s[i - 1] == '1') && k) {
            f[i][j][k] |= f[i - 2][j][k - 1];
          }
          if ((s[i] == '1' && s[i - 1] == '1') && k) {
            f[i][j][k] |= f[i - 1][j + 1][k - 1];
          }
        }
      }
    }
  }
  g[n + 1][0][0] = 1;
  for (int i = n + 1; i > 1; i--) {
    for (int j = 0; j <= n; j++) {
      for (int k = 0; k <= n; k++) {
        Zi v = g[i][j][k];
        if (!v.v)
          continue;
        g[i - 1][j][k] += v;
        if (s[i - 1] == '0')
          g[i][j][k + 1] += v;
        if (s[i - 1] == '1')
          g[i][j + 1][k] += v;
      }
    }
  }
  Zi ans = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      for (int k = 0; k <= i; k++) {
        if (f[i][j][k]) {
          ans += g[i + 1][j][k];
//          cerr << g[i + 1][j][k].v << " " << i + 1 << " " << j << " "<< k << '\n';
        }
      }
    }
  }
//  dfs(string(s + 1));
  printf("%d\n", ans.v);
  return 0;
}

```