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

bool iscat(const string& S_) {
    map<string, int> vis;
    function<bool(const string&)> dfs = [&](const string& S) {
        if (S.empty()) return true;
        if (S[0] != 'm' || S.back() != 'w') return false;
        if (vis.count(S)) return vis[S] == 1;
        rep(i, S.size()) if (S[i] == 'e') {
            if (dfs(S.substr(1, i - 1)) &&
                dfs(S.substr(i + 1, S.size() - i - 2))) {
                vis[S] = 1;
                return true;
            }
        }
        vis[S] = 0;
        return false;
    };
    return dfs(S_);
}

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

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

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_) {
    map<string, int> vis;
    function<bool(const string&)> dfs = [&](const string& S) {
        if (S.empty()) return true;
        if (S[0] != 'm' || S.back() != 'w') return false;
        if (vis.count(S)) return vis[S] == 1;
        rep(i, S.size()) if (S[i] == 'e') {
            if (dfs(S.substr(1, i - 1)) &&
                dfs(S.substr(i + 1, S.size() - i - 2))) {
                vis[S] = 1;
                return true;
            }
        }
        vis[S] = 0;
        return false;
    };
    return dfs(S_);
}

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