#include<iostream>
using namespace std;

string s;
bool memo[500][500] = {}, visit[500][500] = {};

bool cat(int i, int j){
    if(visit[i][j]) return memo[i][j];
    visit[i][j] = true;
    if(i >= j)  return memo[i][j] = true;
    if(s[i] != 'm' || s[j] != 'w')  return memo[i][j] = false;
    bool ret = false;
    for(int k = i+1; k < j; k++){
        if(s[k] == 'e'){
            ret |= (cat(i+1, k-1)&&cat(k+1, j-1));
        }
    }
    return memo[i][j] = ret;
}

int main(){
    cin >> s;
    cout << (cat(0, s.length()-1) ? "Cat" : "Rabbit") << endl;
    return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

string s;
bool memo[500][500] = {}, visit[500][500] = {};

bool cat(int i, int j){
    if(visit[i][j]) return memo[i][j];
    visit[i][j] = true;
    if(i >= j)  return memo[i][j] = true;
    if(s[i] != 'm' || s[j] != 'w')  return memo[i][j] = false;
    bool ret = false;
    for(int k = i+1; k < j; k++){
        if(s[k] == 'e'){
            ret |= (cat(i+1, k-1)&&cat(k+1, j-1));
        }
    }
    return memo[i][j] = ret;
}

int main(){
    cin >> s;
    cout << (cat(0, s.length()-1) ? "Cat" : "Rabbit") << endl;
    return 0;
}

```