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

string S;
int memo[510][510];

int dfs(int l,int r){
    if(l==r)return 1;
    int &ret=memo[l][r];
    if(ret!=-1)return ret;
    ret=0;
    if(S[l]!='m'||S[r-1]!='w')return 0;
    for(int i=l+1;i<r-1;i++){
        if(S[i]!='e')continue;
        ret|=dfs(l+1,i)&&dfs(i+1,r-1);
    }
    return ret;
}

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

Generate a Cpp solution to the following problem:

Example

Input

mmemewwemeww


Output

Cat

### Response

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

string S;
int memo[510][510];

int dfs(int l,int r){
    if(l==r)return 1;
    int &ret=memo[l][r];
    if(ret!=-1)return ret;
    ret=0;
    if(S[l]!='m'||S[r-1]!='w')return 0;
    for(int i=l+1;i<r-1;i++){
        if(S[i]!='e')continue;
        ret|=dfs(l+1,i)&&dfs(i+1,r-1);
    }
    return ret;
}

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