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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
using namespace std;
typedef long long ll;

ll comb[500][10];
ll ans, dif[10];
ll n,m,l;
ll alpha[3][10];
int use[10];

ll calc(void){
  ll dp[10][70] = {};
  rep(i,m)dp[0][i] = 1;

  rep(i,l-1)rep(j,m){
    if(dif[i]==2){
      for(int k=j+2;k<m;k++)dp[i+1][k] += dp[i][j];
    }else{
      if(j+dif[i]<m)dp[i+1][j+dif[i]] += dp[i][j];
    }
  }
  
  ll res = 0;
  rep(i,m)res += dp[l-1][i];

  int len = 1;
  rep(i,l-1){
    if(dif[i]==0)len++;
    else{
      res *= comb[n][len];
      len = 1;
    }
  }
  res *= comb[n][len];

  return res;
}

bool check(int d){
  if(d==3)return true;

  int tmpu[10], tmpa[10];
  rep(i,l){
    int cnt = 0;
    rep(j,l)tmpu[j] = use[j];
    rep(j,10){
      tmpa[j] = alpha[d][j];
      cnt += alpha[d][j];
    }

    int p = i, num = 0, sum = 0;
    while(p<l && tmpa[num]){
      while(p<l && tmpa[num]){
	if(!use[p] && sum == num){
	  use[p] = 1;
	  tmpa[num]--;
	  cnt--;
	}
	sum += dif[p];
	p++;
      }
      num++;
    }

    if(cnt==0 && check(d+1))return true;
    rep(j,l)use[j] = tmpu[j];
  }
  return false;
}

void rec(int d){
  if(d == l-1){
    memset(use,0,sizeof(use));
    if(!check(0))return;

    ans += calc();
    return;
  }

  rep(i,3){
    dif[d] = i;
    rec(d+1);
  }
}

int main(){
  memset(comb,0,sizeof(comb));
  comb[0][0] = 1;
  rep(i,420){
    comb[i+1][0] = 1;
    rep(j,7)comb[i+1][j+1] = comb[i][j+1] + comb[i][j];
  }

  while(cin >> n >> m >> l, n){
    vector<string> h(l);
    rep(i,l)cin >> h[i];
    memset(alpha,0,sizeof(alpha));
    
    rep(i,l){
      if(h[i] == "*")continue;
      int id = h[i][0]-'a';
      alpha[id][h[i].size()-1]++;
    }
    
    ans = 0;
    rec(0);
    cout << fixed << setprecision(9) << (double)ans/comb[n*m][l] << endl;
  }
}