Problem: You have a deck of N × M cards. Each card in the deck has a rank. The range of ranks is 1 through M, and the deck includes N cards of each rank.

We denote a card with rank m by m here.

You can draw a hand of L cards at random from the deck. If the hand matches the given pattern, some bonus will be rewarded. A pattern is described as follows.


hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'


hand_pattern      A hand matches the hand_pattern if each card_pattern in the hand_pattern matches with a distinct card in the hand.  card_pattern      If the card_pattern is an asterisk ('*'), it matches any card. Characters 'a', 'b', and 'c' denote variables and all the occurrences of the same variable match cards of the same rank. A card_pattern with a variable followed by plus ('+') characters matches a card whose rank is the sum of the rank corresponding to the variable and the number of plus characters. You can assume that, when a hand_pattern includes a card_pattern with a variable followed by some number of plus characters, it also includes card_patterns with that variable and all smaller numbers (including zero) of plus characters. For example, if 'a+++' appears in a hand_pattern, card_patterns 'a', 'a+', and 'a++' also appear in the hand_pattern.

There is no restriction on which ranks different variables mean. For example, 'a' and 'b' may or may not match cards of the same rank.

We show some example hand_patterns. The pattern


a * b a b


matches the hand:


3 3 10 10 9


with 'a's and 'b's meaning 3 and 10 (or 10 and 3), respectively. This pattern also matches the following hand.


3 3 3 3 9


In this case, both 'a's and 'b's mean 3. The pattern


a a+ a++ a+++ a++++


matches the following hand.


4 5 6 7 8


In this case, 'a' should mean 4.

Your mission is to write a program that computes the probability that a hand randomly drawn from the deck matches the given hand_pattern.

Input

The input is a sequence of datasets. Each dataset is formatted as follows.

> N M L
>  card_pattern1 card_pattern2 ... card_patternL

The first line consists of three positive integers N, M, and L. N indicates the number of cards in each rank, M indicates the number of ranks, and L indicates the number of cards in a hand. N, M, and L are constrained as follows.

> 1 ≤ N ≤ 7
>  1 ≤ M ≤ 60
>  1 ≤ L ≤ 7
>  L ≤ N × M
>

The second line describes a hand_pattern.

The end of the input is indicated by a line containing three zeros separated by a single space.

Output

For each dataset, output a line containing a decimal fraction which means the probability of a hand matching the hand_pattern.

The output should not contain an error greater than 10−8.

No other characters should be contained in the output.

Sample Input


1 1 1
a
3 3 4
a+ * a *
2 2 3
a a b
2 2 3
* * *
2 2 3
* b b
2 2 2
a a
2 3 3
a a+ a++
2 6 6
a a+ a++ b b+ b++
4 13 5
a a * * *
4 13 5
a a b b *
4 13 5
a a a * *
4 13 5
a a+ a++ a+++ a++++
4 13 5
* * * * *
4 13 5
a a a b b
4 13 5
a a a a *
7 60 7
a b a b c c *
7 60 7
* * * * * * *
7 60 7
a a+ a++ a+++ a++++ a+++++ a++++++
1 14 4
b a+ a a
0 0 0


Output for the Sample Input


1.0000000000
0.8809523810
1.0000000000
1.0000000000
1.0000000000
0.3333333333
0.4000000000
0.1212121212
0.4929171669
0.0492196879
0.0228091236
0.0035460338
1.0000000000
0.0014405762
0.0002400960
0.0002967709
1.0000000000
0.0000001022
0.0000000000






Example

Input

1 1 1
a
3 3 4
a+ * a *
2 2 3
a a b
2 2 3
* * *
2 2 3
* b b
2 2 2
a a
2 3 3
a a+ a++
2 6 6
a a+ a++ b b+ b++
4 13 5
a a * * *
4 13 5
a a b b *
4 13 5
a a a * *
4 13 5
a a+ a++ a+++ a++++
4 13 5
* * * * *
4 13 5
a a a b b
4 13 5
a a a a *
7 60 7
a b a b c c *
7 60 7
* * * * * * *
7 60 7
a a+ a++ a+++ a++++ a+++++ a++++++
1 14 4
b a+ a a
0 0 0


Output

1.0000000000
0.8809523810
1.0000000000
1.0000000000
1.0000000000
0.3333333333
0.4000000000
0.1212121212
0.4929171669
0.0492196879
0.0228091236
0.0035460338
1.0000000000
0.0014405762
0.0002400960
0.0002967709
1.0000000000
0.0000001022
0.0000000000

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

ll nCk(int n,int k){
  if(n<k)return 0;
  ll res = 1;
  for(int i=n-k+1;i<=n;i++)res*=i;
  for(int i=1;i<=k;i++)res/=i;
  return res;
}

int N,M,L;
vector<string> in;
int a[10],b[10],c[10];
void start_init(){
  N=M=L=0;
  in.clear();
  for(int i=0;i<10;i++){
    a[i]=b[i]=c[i]=0;
  }
}

int input(){
  cin>>N>>M>>L;
  if(N==0&&M==0&&L==0)return false;
  in.clear();in.resize(L);
  for(int i=0;i<L;i++){
    cin>>in[i];
  }
  return true;
}

bool over(vector<int>& n,vector<int>& h){
  for(int i=0;i<n.size();i++){
    if(n[i]>h[i]){
      return true;
    }
  }
  return false;
}
bool match(vector<int>& hand,vector<int>& h){
  //cerr<<" h[0]::"<<h[0];
  for(int i=0;i<h.size();i++){
    if(h[i]>N){
      return false;
    }
  }
  for(int i=0;i<hand.size();i++){
    for(int j=0;j<hand.size();j++){
      for(int k=0;k<hand.size();k++){
        vector<int> n(20,0);
        for(int l=0;l<10;l++){
          n[hand[i]+l] += a[l];
          n[hand[j]+l] += b[l];
          n[hand[k]+l] += c[l];
        }
        if(!over(n,h))return true;
      }
    }
  }
  return false;
}
ll count(vector<int>& hands,vector<int>& h,int s){
  ll res = 1;
  for(int i=0;i<h.size();i++){
    res *= nCk(N,h[i]);
  }
  const int c = M - (hands[hands.size()-1] + 1) + s;
  res *= nCk(c,s);
  ////cerr<<"count::"<<res<<endl;
  return res;
}

void print(vector<int> h){
  for(auto i:h){
    //cerr<<i<<" ";
  }
}

ll ans = 0;
vector<int> hands;
void init(){
  ans = 0;
  hands = vector<int>(L,0);
  for(int i=0;i<10;i++){
    a[i]=b[i]=c[i]=0;
  }
  sort(in.begin(),in.end());
  for(auto i:in){
    switch(i[0]){
      case 'a':
        a[i.size()-1]++;
        break;
      case 'b':
        b[i.size()-1]++;
        break;
      case 'c':
        c[i.size()-1]++;
        break;
    }
  }
}

void solve(int n,int startings){
  if(!(hands[n-1]<M)){
    //cerr<<"number err "<<n<<"::";print(hands);//cerr<<endl;
    return;
  }
  if(n==L){
    vector<int> h(20,0);
    for(int i=0;i<hands.size();i++){
      h[hands[i]]++;
    }
    //cerr<<"match    ::"<<n<<"::";print(hands);
    if(match(hands,h)){
      //cerr<<" true::";
      ll tmp = count(hands,h,startings);
      //cerr<<tmp;
      ans += tmp;
    }
    //cerr<<endl;
    return;
  }
  //cerr<<"pass     ::"<<n<<"::";print(hands);//cerr<<endl;
  hands[n] = hands[n-1];
  solve(n+1,startings);
  hands[n] = hands[n-1]+1;
  solve(n+1,startings);
  hands[n] = hands[n-1]+2;
  solve(n+1,startings+1);
}

void printabc(){
  //cerr<<"a:";
  for(int i=0;i<7;i++){
    //cerr<<a[i]<<" ";
  }//cerr<<endl;
  //cerr<<"b:";
  for(int i=0;i<7;i++){
    //cerr<<b[i]<<" ";
  }//cerr<<endl;
  //cerr<<"c:";
  for(int i=0;i<7;i++){
    //cerr<<c[i]<<" ";
  }//cerr<<endl;
}

int main(){
  while(start_init(),input()){
    init();
    solve(1,1);
    /*
    cout<<N<<" "<<M<<" "<<L<<endl;
    for(auto i:in){
      cout<<i<<" ";
    }cout<<endl;
    */
    printabc();
    cout<<fixed<<setprecision(10)<<(double(ans))/(nCk(N*M,L))<<endl;
  }
}