#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define mod 20071027 #define M 400005 using namespace std; int n,top,len; int tree[M][27]; char S[M]; char p[105]; int val[M]; int d[M]; void init() { top=1; memset(tree,0,sizeof(tree)); memset(d,0,sizeof(d)); } int idx(char c) { return c-'a'; } void insert(char *s) { int Len=strlen(s); int u=0; for(int i=0;i<Len;i++) { int c=idx(s[i]); if(!tree[u][c]) { val[top]=0; tree[u][c]=top++; } u=tree[u][c]; } val[u]=1; } int query(char *s,int start) { int count=0; int u=0; for(int i=start;i<len;i++) { int c=idx(s[i]); u=tree[u][c]; if(!u) return count; if(val[u]) { count+=d[i+1]; count%=mod; } } return count; } int main() { int t=1; //freopen("d: est.txt","r",stdin); while(scanf("%s",S)!=EOF) { scanf("%d",&n); init(); for(int i=0;i<n;i++) { scanf("%s",p); insert(p); } len=strlen(S); d[len]=1; for(int i=1;i<=len;i++) { d[len-i]=query(S,len-i); } cout<<"Case "<<t++<<": "<<d[0]<<endl; } return 0; }