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

int dp[505][505];

int check(const string &s, int l, int r){
    // cerr << l << " " << r << endl;
    int f;
    if(l == r)f = 1;
    else if(dp[l][r] != -1)f = dp[l][r];
    else if(s[l] != 'm' || s[r-1] != 'w')f = 0;
    else{
        f = 0;
        for(int i=l;i<r;i++){
            if(s[i] == 'e' && check(s, l+1, i) && check(s, i+1, r-1))f = 1;
        }
    }
    return dp[l][r] = f;
}

int main(void){
    string s;
    cin >> s;
    for(int i=0;i<505;i++)for(int j=0;j<505;j++)dp[i][j] = -1;
    bool f = check(s, 0, s.length());
    // for(int i=0;i<=s.length();i++){
    //     for(int j=0;j<=s.length();j++)cerr << dp[i][j] << " ";
    //     cerr << endl;
    // }
    if(f)cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
}

### Prompt

Construct a cpp code solution to the problem outlined:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

int dp[505][505];

int check(const string &s, int l, int r){
    // cerr << l << " " << r << endl;
    int f;
    if(l == r)f = 1;
    else if(dp[l][r] != -1)f = dp[l][r];
    else if(s[l] != 'm' || s[r-1] != 'w')f = 0;
    else{
        f = 0;
        for(int i=l;i<r;i++){
            if(s[i] == 'e' && check(s, l+1, i) && check(s, i+1, r-1))f = 1;
        }
    }
    return dp[l][r] = f;
}

int main(void){
    string s;
    cin >> s;
    for(int i=0;i<505;i++)for(int j=0;j<505;j++)dp[i][j] = -1;
    bool f = check(s, 0, s.length());
    // for(int i=0;i<=s.length();i++){
    //     for(int j=0;j<=s.length();j++)cerr << dp[i][j] << " ";
    //     cerr << endl;
    // }
    if(f)cout << "Cat" << endl;
    else cout << "Rabbit" << endl;
}

```