#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[501][501];
bool dfs(string &s,int from,int to){
  if(dp[from][to]>=0)return dp[from][to];
  if(s=="")return true;
  else if(s.size()<=2)return false;
  else if(s[0]!='m'||s[s.size()-1]!='w')return false;
  for(int i=1;i<s.size()-1;i++){
    if(s[i]!='e')continue;
    string X=s.substr(1,i-1);
    string Y=s.substr(i+1);Y=Y.substr(0,Y.size()-1);
    if((X==""||dfs(X,from+1,from+i-1))
       &&(Y==""||dfs(Y,from+i+1,from+s.size()-2)))
      return dp[from][to]=true;
  }
  return dp[from][to]=false;
}

int main(){

  string S;
  cin>>S;
  memset(dp,-1,sizeof(dp));
  if(dfs(S,0,S.size()-1))cout<<"Cat"<<endl;
  else cout<<"Rabbit"<<endl;

  return 0;
}
### Prompt

Construct a CPP code solution to the problem outlined:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>

using namespace std;

int dp[501][501];
bool dfs(string &s,int from,int to){
  if(dp[from][to]>=0)return dp[from][to];
  if(s=="")return true;
  else if(s.size()<=2)return false;
  else if(s[0]!='m'||s[s.size()-1]!='w')return false;
  for(int i=1;i<s.size()-1;i++){
    if(s[i]!='e')continue;
    string X=s.substr(1,i-1);
    string Y=s.substr(i+1);Y=Y.substr(0,Y.size()-1);
    if((X==""||dfs(X,from+1,from+i-1))
       &&(Y==""||dfs(Y,from+i+1,from+s.size()-2)))
      return dp[from][to]=true;
  }
  return dp[from][to]=false;
}

int main(){

  string S;
  cin>>S;
  memset(dp,-1,sizeof(dp));
  if(dfs(S,0,S.size()-1))cout<<"Cat"<<endl;
  else cout<<"Rabbit"<<endl;

  return 0;
}
```