#include<stdio.h>
#include<string.h>
char str[512];
int n;
int dp[500][500];
int solve(int a,int b){
	if(a==b)return 1;
	if(~dp[a][b])return dp[a][b];
	if(str[a]!='m'||str[b-1]!='w')return 0;
	for(int i=a+1;i<b-1;i++){
		if(str[i]=='e'){
			int v=solve(a+1,i)&solve(i+1,b-1);
			if(v)return dp[a][b]=1;
		}
	}
	return dp[a][b]=0;
}
int main(){
	scanf("%s",str);
	n=strlen(str);
	for(int i=0;i<500;i++)
		for(int j=0;j<500;j++)
			dp[i][j]=-1;
	printf("%s\n",solve(0,n)?"Cat":"Rabbit");
}
### Prompt

Develop a solution in cpp to the problem described below:

Example

Input

mmemewwemeww


Output

Cat

### Response

```cpp
#include<stdio.h>
#include<string.h>
char str[512];
int n;
int dp[500][500];
int solve(int a,int b){
	if(a==b)return 1;
	if(~dp[a][b])return dp[a][b];
	if(str[a]!='m'||str[b-1]!='w')return 0;
	for(int i=a+1;i<b-1;i++){
		if(str[i]=='e'){
			int v=solve(a+1,i)&solve(i+1,b-1);
			if(v)return dp[a][b]=1;
		}
	}
	return dp[a][b]=0;
}
int main(){
	scanf("%s",str);
	n=strlen(str);
	for(int i=0;i<500;i++)
		for(int j=0;j<500;j++)
			dp[i][j]=-1;
	printf("%s\n",solve(0,n)?"Cat":"Rabbit");
}
```