#include<iostream>
#include<string.h>
using namespace std;

const int mod=10007;
int dp[1009][1009];

int main(){
	int t;int ca=0;
	while(~scanf("%d",&t)){
		ca++;
		string ss;cin>>ss;
//		cout<<ss<<endl;
		int sz=ss.size();
		memset(dp,0,sizeof(dp));
		for(int i=0;i<sz;i++){
			dp[i][i]=1;
		}
		for(int j=0;j<sz;j++){
			for(int i=j-1;i>=0;i--){
				dp[i][j]=(dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1]+mod)%mod;
				if(ss[i]==ss[j]) dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1+mod)%mod;
			}
		}
		printf("Case %d: %d\n",ca,dp[0][sz-1]);
	}
}