#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

int dp[500][501];

int is_cat(string &S, int L, int R) {
  if(L > R) return true;
  if(S[L] != 'm') return dp[L][R] = false;
  if(S[R] != 'w') return dp[L][R] = false;
  if(~dp[L][R]) return dp[L][R];
  for(int i = L + 1; i + 1 <= R; i++) {
    if(is_cat(S, L + 1, i - 1) && S[i] == 'e' && is_cat(S, i + 1, R - 1)) {
      return dp[L][R] = true;
    }
  }
  return dp[L][R] = false;
}

int main() {
  memset(dp, -1, sizeof(dp));
  string S;
  cin >> S;
  if(is_cat(S, 0, S.size() - 1)) cout << "Cat\n";
  else cout << "Rabbit\n";
}



### Prompt

Please formulate a CPP solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<bits/stdc++.h>

using namespace std;

using int64 = long long;

int dp[500][501];

int is_cat(string &S, int L, int R) {
  if(L > R) return true;
  if(S[L] != 'm') return dp[L][R] = false;
  if(S[R] != 'w') return dp[L][R] = false;
  if(~dp[L][R]) return dp[L][R];
  for(int i = L + 1; i + 1 <= R; i++) {
    if(is_cat(S, L + 1, i - 1) && S[i] == 'e' && is_cat(S, i + 1, R - 1)) {
      return dp[L][R] = true;
    }
  }
  return dp[L][R] = false;
}

int main() {
  memset(dp, -1, sizeof(dp));
  string S;
  cin >> S;
  if(is_cat(S, 0, S.size() - 1)) cout << "Cat\n";
  else cout << "Rabbit\n";
}



```