#include <bits/stdc++.h>

using namespace std;

string S;
int dp[512][512];

bool solve(int l, int r)
{
  if(~dp[l][r]) return dp[l][r];
  if(l == r) return dp[l][r] = 1;
  if(S[l] != 'm' || S[r-1] != 'w') return dp[l][r] = 0;
  int ret = 0;
  for(int m = l+1; m < r-1; m++){
    if(S[m] == 'e'){
      ret |= solve(l+1, m) & solve(m+1, r-1);
    }
  }
  return dp[l][r] = ret;
}

int main()
{
  cin >> S;
  fill(dp[0], dp[512], -1);
  if(solve(0, S.size())) cout << "Cat" << endl;
  else cout << "Rabbit" << endl;
  return 0;
}
### Prompt

Create a solution in CPP for the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

using namespace std;

string S;
int dp[512][512];

bool solve(int l, int r)
{
  if(~dp[l][r]) return dp[l][r];
  if(l == r) return dp[l][r] = 1;
  if(S[l] != 'm' || S[r-1] != 'w') return dp[l][r] = 0;
  int ret = 0;
  for(int m = l+1; m < r-1; m++){
    if(S[m] == 'e'){
      ret |= solve(l+1, m) & solve(m+1, r-1);
    }
  }
  return dp[l][r] = ret;
}

int main()
{
  cin >> S;
  fill(dp[0], dp[512], -1);
  if(solve(0, S.size())) cout << "Cat" << endl;
  else cout << "Rabbit" << endl;
  return 0;
}
```