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

using namespace std;

string s;

int dp[512][512];

int solve(int l, int r){
    int & res = dp[l][r];
    if (res != -1) return res;
    
    if (l == r) res = true;
    else if (r - l < 3) res = false;
    else if (r - l == 3) res = s.substr(l, 3) == "mew";
    else if (s[l] != 'm' || s[r - 1] != 'w') res = false;
    else {
        res = false;
        for (int i = l + 1; i < r; i++){
            if (s[i] == 'e'){
                if (solve(l + 1, i) && solve(i + 1, r - 1)) {
                    res = true;
                    break;
                }
            }
        }
    }
    return res;
}

int main(){
    while (cin >> s){
        memset(dp, -1, sizeof(dp));
        cout << (solve(0, s.size()) ? "Cat" : "Rabbit") << endl;
    }
}
### Prompt

Please formulate a Cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

using namespace std;

string s;

int dp[512][512];

int solve(int l, int r){
    int & res = dp[l][r];
    if (res != -1) return res;
    
    if (l == r) res = true;
    else if (r - l < 3) res = false;
    else if (r - l == 3) res = s.substr(l, 3) == "mew";
    else if (s[l] != 'm' || s[r - 1] != 'w') res = false;
    else {
        res = false;
        for (int i = l + 1; i < r; i++){
            if (s[i] == 'e'){
                if (solve(l + 1, i) && solve(i + 1, r - 1)) {
                    res = true;
                    break;
                }
            }
        }
    }
    return res;
}

int main(){
    while (cin >> s){
        memset(dp, -1, sizeof(dp));
        cout << (solve(0, s.size()) ? "Cat" : "Rabbit") << endl;
    }
}
```