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

int memo[500][500];

bool check(string str, int start)
{
	bool flag = false;

	if (str.empty() == true) {
		flag = true;
	}
	else {
		if (memo[start][str.size()] == 1) {
			return true;
		}
		else if (memo[start][str.size()] == 0) {
			return false;
		}
		else {
			if (str.front() == 'm'&&str.back() == 'w') {
				for (int i = 0; i < str.size(); i++) {
					if (str[i] == 'e') {
						if (check(str.substr(1, i - 1), start + 1) && check(str.substr(i + 1, str.size() - i - 2), start + i + 1)) {
							flag = true;
							break;
						}
					}
				}
			}
		}
	}

	if (flag == true) {
		memo[start][str.size()] = 1;
	}
	else {
		memo[start][str.size()] = 0;
	}

	return flag;
}

int main()
{
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++) {
			memo[i][j] = -1;
		}
	}

	string S;
	cin >> S;

	bool flag = check(S, 0);

	if (flag == true) {
		cout << "Cat" << endl;
	}
	else {
		cout << "Rabbit" << endl;
	}

	return 0;
}
### Prompt

In Cpp, your task is to solve the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

int memo[500][500];

bool check(string str, int start)
{
	bool flag = false;

	if (str.empty() == true) {
		flag = true;
	}
	else {
		if (memo[start][str.size()] == 1) {
			return true;
		}
		else if (memo[start][str.size()] == 0) {
			return false;
		}
		else {
			if (str.front() == 'm'&&str.back() == 'w') {
				for (int i = 0; i < str.size(); i++) {
					if (str[i] == 'e') {
						if (check(str.substr(1, i - 1), start + 1) && check(str.substr(i + 1, str.size() - i - 2), start + i + 1)) {
							flag = true;
							break;
						}
					}
				}
			}
		}
	}

	if (flag == true) {
		memo[start][str.size()] = 1;
	}
	else {
		memo[start][str.size()] = 0;
	}

	return flag;
}

int main()
{
	for (int i = 0; i < 500; i++) {
		for (int j = 0; j < 500; j++) {
			memo[i][j] = -1;
		}
	}

	string S;
	cin >> S;

	bool flag = check(S, 0);

	if (flag == true) {
		cout << "Cat" << endl;
	}
	else {
		cout << "Rabbit" << endl;
	}

	return 0;
}
```