#include <bits/stdc++.h>

#define DEBUG(C) cerr << #C << " = " << C << endl

using namespace std;

string S;
int dp[555][555];
bool f(int l, int r) { //[l, r)
//  cerr << dp[l][r] << endl;
//  cerr << l << " " << r << endl;
  if (dp[l][r] != -1) {
    return dp[l][r];
  }
  if (l == r) {
    return dp[l][r] = 1;
  }
  if (S[l] != 'm' || S[r - 1] != 'w') {
    return dp[l][r] = 0;
  }
  bool res = false;
  for (int i = l + 1; i < r - 1; i++) {
    if (S[i] == 'e') {
      res |= (f(l + 1, i) && f(i + 1, r - 1));
    }
  }
  return dp[l][r] = res;
}

int main() {
  cin >> S;
  memset(dp, -1, sizeof(dp));
  cout << (f(0, S.length()) ? "Cat" : "Rabbit") << endl;
  return 0;
}
### Prompt

Develop a solution in cpp to the problem described below:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>

#define DEBUG(C) cerr << #C << " = " << C << endl

using namespace std;

string S;
int dp[555][555];
bool f(int l, int r) { //[l, r)
//  cerr << dp[l][r] << endl;
//  cerr << l << " " << r << endl;
  if (dp[l][r] != -1) {
    return dp[l][r];
  }
  if (l == r) {
    return dp[l][r] = 1;
  }
  if (S[l] != 'm' || S[r - 1] != 'w') {
    return dp[l][r] = 0;
  }
  bool res = false;
  for (int i = l + 1; i < r - 1; i++) {
    if (S[i] == 'e') {
      res |= (f(l + 1, i) && f(i + 1, r - 1));
    }
  }
  return dp[l][r] = res;
}

int main() {
  cin >> S;
  memset(dp, -1, sizeof(dp));
  cout << (f(0, S.length()) ? "Cat" : "Rabbit") << endl;
  return 0;
}
```