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

int memo[501][501];
string in;

int solve(int s,int t) {
    if(s == t) return memo[s][t] = 1;
    if(memo[s][t] != 0) return memo[s][t];

    if(in[s] != 'm' || in[t-1] != 'w') return memo[s][t] = 2;

    for(int e = s+1; e < t-1; ++e)
        if(in[e] == 'e') {
            if(solve(s+1,e) == 1 && solve(e+1,t-1) == 1)
                return memo[s][t] = 1;
        }

    return memo[s][t] = 2;
}

int main() {
    memset(memo, 0, sizeof(memo));

    cin>>in;
    if(solve(0,in.length()) == 1) cout<<"Cat"<<endl;
    else cout<<"Rabbit"<<endl;
}
### Prompt

Please provide a cpp coded solution to the problem described below:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

int memo[501][501];
string in;

int solve(int s,int t) {
    if(s == t) return memo[s][t] = 1;
    if(memo[s][t] != 0) return memo[s][t];

    if(in[s] != 'm' || in[t-1] != 'w') return memo[s][t] = 2;

    for(int e = s+1; e < t-1; ++e)
        if(in[e] == 'e') {
            if(solve(s+1,e) == 1 && solve(e+1,t-1) == 1)
                return memo[s][t] = 1;
        }

    return memo[s][t] = 2;
}

int main() {
    memset(memo, 0, sizeof(memo));

    cin>>in;
    if(solve(0,in.length()) == 1) cout<<"Cat"<<endl;
    else cout<<"Rabbit"<<endl;
}
```