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:
//copied from http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1635223#1
//my source code is http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3712456#1

#include<stdio.h>
#include<algorithm>
using namespace std;
char in[10][10];
int pl[10];
int u[10][10];
int t3[10];
int q[10];
int used[10];
int L;
int dfs(int a){
    if(a==3){
        return 1;
    }
    if(u[a][0]==0)return dfs(a+1);
    for(int i=0;i<L;i++){
        if(used[i])continue;
        bool ok=true;
        for(int j=0;j<L;j++){
            int cnt=0;
            for(int k=0;k<L;k++){
                if(!used[k]&&q[k]==q[i]+j)cnt++;
            }
            if(cnt<u[a][j])ok=false;
        }
        if(ok){
            for(int j=0;j<L;j++){
                int cnt=0;
                for(int k=0;k<L;k++){
                    if(cnt==u[a][j])break;
                    if(!used[k]&&q[k]==q[i]+j){
                        cnt++;
                        used[k]=1;
                    }
                }
            }
            if(dfs(a+1))return 1;
            for(int j=0;j<L;j++){
                int cnt=0;
                for(int k=0;k<L;k++){
                    if(cnt==u[a][j])break;
                    if(used[k]&&q[k]==q[i]+j){
                        cnt++;
                        used[k]=0;
                    }
                }
            }
        }
    }
    return 0;
}
long long C[10][10];
int main(){
    int a,b,c;
    t3[0]=1;
    C[0][0]=1;
    for(int i=0;i<9;i++){
        for(int j=0;j<=i;j++){
            C[i+1][j]+=C[i][j];
            C[i+1][j+1]+=C[i][j];
        }
    }
    for(int i=1;i<10;i++)t3[i]=t3[i-1]*3;
    while(scanf("%d%d%d",&a,&b,&c),a){
        L=c;
        for(int i=0;i<10;i++)for(int j=0;j<10;j++)u[i][j]=0;
        for(int i=0;i<c;i++){
            scanf("%s",in[i]);
            pl[i]=0;
            for(int j=1;in[i][j];j++)pl[i]++;
            if(in[i][0]!='*')u[in[i][0]-'a'][pl[i]]++;
        }
    /*  for(int i=0;i<3;i++){
            for(int j=0;j<7;j++)printf("%d ",u[i][j]);
            printf("\n");
        }*/
        long long ret=0;
        for(int i=0;i<t3[c-1];i++){
            q[0]=0;
            for(int j=0;j<c;j++)used[j]=0;
            for(int j=1;j<c;j++){
                q[j]=q[j-1]+i%t3[j]/t3[j-1];
            }
            if(!dfs(0))continue;
            long long tmp=1;
            int now=0;
            int div=1;
            int num=1;
            for(int j=0;j<c;j++){
                if(j&&q[j]!=q[j-1]){
                    tmp*=C[a][now];
                    now=1;
                    num++;
                    if(q[j-1]+1<q[j])div++;
                }else now++;
            }
            tmp*=C[a][now];
            int un=b-num;
            if(un<div-1)continue;
            un-=div-1;
            for(int j=0;j<div;j++){
                tmp*=(un+div-j);
                tmp/=(j+1);
            }
        //  for(int j=0;j<c;j++)printf("%d ",q[j]);
        //  printf(": %lld\n",tmp);
            ret+=tmp;
        }
        long long total=1;
        for(int i=0;i<c;i++){
            total*=(a*b-i);
            total/=(i+1);
        }
        printf("%.12f\n",(double)ret/total);
    }
}