#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

bool iscat(const string& S) {
    vector<vector<int>> mem(S.size(), vector<int>(S.size() + 1, -1));
    function<bool(int, int)> dfs = [&](int p, int l) {
        if (l <= 0) return true;
        if (S[p] != 'm' || S[p + l - 1] != 'w') return false;
        if (mem[p][l] != -1) return mem[p][l] == 1;
        rep(i, l) if (S[p + i] == 'e') {
            if (dfs(p + 1, i - 1) && dfs(p + i + 1, l - i - 2)) return mem[p][l] = 1, true;
        }
        mem[p][l] = 0;
        return false;
    };
    return dfs(0, S.size());
}

int main() {
    string S; cin >> S;
    cout << (iscat(S) ? "Cat" : "Rabbit") << endl;
}
### Prompt

Your task is to create a CPP solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); ++i)

bool iscat(const string& S) {
    vector<vector<int>> mem(S.size(), vector<int>(S.size() + 1, -1));
    function<bool(int, int)> dfs = [&](int p, int l) {
        if (l <= 0) return true;
        if (S[p] != 'm' || S[p + l - 1] != 'w') return false;
        if (mem[p][l] != -1) return mem[p][l] == 1;
        rep(i, l) if (S[p + i] == 'e') {
            if (dfs(p + 1, i - 1) && dfs(p + i + 1, l - i - 2)) return mem[p][l] = 1, true;
        }
        mem[p][l] = 0;
        return false;
    };
    return dfs(0, S.size());
}

int main() {
    string S; cin >> S;
    cout << (iscat(S) ? "Cat" : "Rabbit") << endl;
}
```