HDU4639+字符串

/*
字符串
*/
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<stack>
#include<set>
#include<math.h>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int maxn = 10090;
const int mod = 10007;
const int inf = 0x7fffffff;
const double pi=acos(-1.0);
const double eps = 1e-8;
int Fib[ maxn ];
void init(){
	Fib[ 0 ] = 1;
	Fib[ 1 ] = 1;
	for( int i=2;i<maxn;i++ ){
		Fib[i] = Fib[i-1]+Fib[i-2];
		Fib[i] %= mod;
	}
}
int main(){
	init();
	int Case = 1;
	int T;
	scanf("%d",&T);
	while( T-- ){
		char s[ maxn ];
		printf("Case %d: ",Case++);
		int ans = 1;
		scanf("%s",s);
		int len = strlen(s);
		for( int i=0;i<len;i++ ){
			int cnt = 0;
			if( i+1<len&&s[i]=='h'&&s[i+1]=='e' ){
				//cnt = 1;
				int Index = i;
				bool f = false;
				while( Index+1<len ){
					if( s[Index]=='h'&&s[Index+1]=='e' ){
						cnt ++ ;
						Index += 2;
						i = Index;
					}
					else{
						if( cnt ) i--;
						if( cnt ) ans = ans*Fib[ cnt ]%mod;
						f = true;
						break;
					}
				}
				if( f==false&&cnt )  ans = ans*Fib[ cnt ]%mod;
			}
		}
		printf("%d\n",max(ans%mod,1));
	}
	return 0;
}