#include<iostream>
#include<string>
#include<map>
using namespace std;

map<string,bool> memo;

bool cat(string s){
  if(s.empty())return true;
  if(memo.find(s)!=memo.end())return memo[s];
  int n = s.size()-1;
  if(s[0] != 'm' || s[n] != 'w')return false;

  for(int i=0;i<n;i++){
    if(s[i] == 'e'){
      if(cat(s.substr(1,i-1)) && cat(s.substr(i+1,n-i-1)))return memo[s] = true;
    }
  }
  return memo[s] = false;
}

int main(){
  string s;
  cin >> s;
  cout << (cat(s)?"Cat":"Rabbit") << endl;
}
### Prompt

Your challenge is to write a CPP solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<iostream>
#include<string>
#include<map>
using namespace std;

map<string,bool> memo;

bool cat(string s){
  if(s.empty())return true;
  if(memo.find(s)!=memo.end())return memo[s];
  int n = s.size()-1;
  if(s[0] != 'm' || s[n] != 'w')return false;

  for(int i=0;i<n;i++){
    if(s[i] == 'e'){
      if(cat(s.substr(1,i-1)) && cat(s.substr(i+1,n-i-1)))return memo[s] = true;
    }
  }
  return memo[s] = false;
}

int main(){
  string s;
  cin >> s;
  cout << (cat(s)?"Cat":"Rabbit") << endl;
}
```