// ACM problem
// 2005 ECNA ACm regional coontest
// t feil

#include <iostream>
using namespace std;

int A[20][200][200], GRID[200][200];
char word[200][250], Abr[200], insig[200][200];
int Count, k, n, m, X[200], InSigNo;

int GetAbr(){
  cin>>Abr;
  return strlen(Abr);
}

bool Sig(char w[100]){
  for(int i=0;i<InSigNo;i++)
    if(strcmp(w,insig[i])==0) return false;
  return true;
}

int GetPhrase(){
  int k=0;
  char w[100];

  while(cin.peek() !='\n'){
    cin>>word[k];
//cout<<word[k];
    if(Sig(word[k])){
//cout <<"sig";
      k++;
    }
//cout<<endl;
  }
  //read that last '\n'
  char c= getchar();
  return k;
}

void zeroA(int k){
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      A[k][i][j]=0;
}

void zeroGRID(){
  for(int i=0;i<m;i++)
    for(int j=0;j<n;j++)
      GRID[i][j]=0;
}

void printGRID(){
  for(int i=0;i<m;i++){
    for(int j=0;j<n;j++)
      cout<<GRID[i][j]<<' ';
    cout<<endl;
  }
  cout<<endl;
}
void makeA(int w){
//cout<<word[w]<<' '<<Abr<<endl;
  zeroA(w);
  m=strlen(word[w]);
   int START = n-1;
  while(START>=0){
    zeroGRID();
    for(int i=START;i>=0;i--){ //look for letter Abr[i] in word[w]
      for(int j=m-1;j>=0;j--)
        if(word[w][j]==tolower(Abr[i]))
          if(i==START) GRID[j][i]=1;
          else //look over next col and down
          { int count=0, k=j+1;
            while(k<m) count += GRID[k++][i+1];
            GRID[j][i] = count;
          }
     }
//cout<<"print GRID "<<START<<endl;
//printGRID();
      //now can fill in START col of A[w]
      for(int i=0;i<=START;i++){ //do col i of A[][START]
        int sum=0;
        for(int j=0;j<m;j++) sum += GRID[j][i];
        A[w][i][START]=sum;
      } 
    START--;
  }
}

void printA(int k){
  for(int i=0;i<n;i++){
    for(int j=0;j<n;j++)
      cout<<A[k][i][j]<<' '; 
    cout<<endl;
  }
  cout<<endl;
}

int main(){
  int Subs[20];

  //get list of insignifican words
  cin>>InSigNo;
  while (InSigNo>0){
// cout<<"n="<<n<<" k="<<k<<endl;

  for(int i=0;i<InSigNo;i++)
    cin>>insig[i];

  n = GetAbr();
  k = GetPhrase();
  
   while(1) { //go until see "LAST CASE"

    if(n<k) cout<<Abr<<" is not a valid abbreviation"<<endl;
    else {

    for(int w=0;w<k;w++){
      makeA(w);
//cout<<"made A["<<w<<']'<<endl;
//      printA(w);
    }

    // now calculate number of words via "multiplication" of the A's
    for(int i=0;i<n;i++) Subs[i]=A[0][0][i]; // initialize array - Subs[n-1] is what we'll want
    for(int i=1;i<k;i++){  // "mult' Subs by A[i]
     for(int j=n-1; j>=i;j--){ //calc new Subs[j]
      int sum=0;
      for(int p=i-1;p<j; p++) sum += Subs[p]*A[i][p+1][j];
      Subs[j]=sum;
     }
// cout<<"Subs "<<i<<' '; for(int j=0;j<n;j++) cout<<Subs[j]<<' '; cout<<endl;
    }
    //now print result
    if(Subs[n-1]==0) cout<<Abr<<" is not a valid abbreviation"<<endl;
    else cout<<Abr<<" can be formed in "<<Subs[n-1]<<" ways"<<endl;
    }

    n = GetAbr();
    k = GetPhrase();
    if(strcmp(Abr,"LAST")==0 && strcmp(word[0],"CASE")==0 && k==1){
     //end of this case; get more insignificant words
      cin>>InSigNo;
      break;
    }
}
    
/*
    for(int i=0;i<InSigNo;i++)
      cin>>insig[i];

     n = GetAbr();
     k = GetPhrase();
*/
  }

return 0;
}