#include <iostream>
#include <string>

using namespace std;

string S;

char dp[501][501];

char dfs(int l, int r){
    //cout << "dfs: " << l << "," << r << endl;
    if(dp[l][r] != -1){
        return dp[l][r];
    }
    if(l == r){
        return dp[l][r] = 1;
    }else if(r - l == 1 || r - l == 2){
        return dp[l][r] = 0;
    }
    if(!(S[l] == 'm' && S[r-1] == 'w')){
        return dp[l][r] = 0;
    }
    for(int i = l + 1; i < r-1;i++){
        if(S[i] != 'e') continue;
        if(dfs(l + 1,i) && dfs(i+1,r - 1)){
            return dp[l][r] = 1;
        }
    }
    return dp[l][r] = 0;
}

int main(){
    cin >> S;
    for(int i = 0;i<501;i++)for(int j = 0;j<501;j++){
        dp[i][j] = -1;
    }
    if(dfs(0,S.size()) == 1){
        cout << "Cat" << endl;
    }else{
        cout << "Rabbit" << endl;
    }
}
### Prompt

Please create a solution in cpp to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

using namespace std;

string S;

char dp[501][501];

char dfs(int l, int r){
    //cout << "dfs: " << l << "," << r << endl;
    if(dp[l][r] != -1){
        return dp[l][r];
    }
    if(l == r){
        return dp[l][r] = 1;
    }else if(r - l == 1 || r - l == 2){
        return dp[l][r] = 0;
    }
    if(!(S[l] == 'm' && S[r-1] == 'w')){
        return dp[l][r] = 0;
    }
    for(int i = l + 1; i < r-1;i++){
        if(S[i] != 'e') continue;
        if(dfs(l + 1,i) && dfs(i+1,r - 1)){
            return dp[l][r] = 1;
        }
    }
    return dp[l][r] = 0;
}

int main(){
    cin >> S;
    for(int i = 0;i<501;i++)for(int j = 0;j<501;j++){
        dp[i][j] = -1;
    }
    if(dfs(0,S.size()) == 1){
        cout << "Cat" << endl;
    }else{
        cout << "Rabbit" << endl;
    }
}
```