#include<bits/stdc++.h>
using namespace std;

string S;
int dp[511][511];
int solve(int l,int r){
  if( dp[l][r] != -1 ) return dp[l][r];
  if( l > r ) return true;
  if( S[l] == 'm' && S[r] == 'w' )
    for(int i=l+1;i<r;i++)
      if( S[i] == 'e' )
	if( solve(l+1,i-1) && solve(i+1,r-1) ) return dp[l][r] = 1;	
  return dp[l][r] = 0;
}

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

Please formulate a cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<bits/stdc++.h>
using namespace std;

string S;
int dp[511][511];
int solve(int l,int r){
  if( dp[l][r] != -1 ) return dp[l][r];
  if( l > r ) return true;
  if( S[l] == 'm' && S[r] == 'w' )
    for(int i=l+1;i<r;i++)
      if( S[i] == 'e' )
	if( solve(l+1,i-1) && solve(i+1,r-1) ) return dp[l][r] = 1;	
  return dp[l][r] = 0;
}

int main(){
  memset(dp,-1,sizeof(dp));
  cin >> S;
  if( solve(0,S.size()-1) )
    cout << "Cat" << endl;
  else
    cout << "Rabbit" << endl;
  
}
```