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;

#define REP(i,n) for(int i=0; i<n; i++)
#define FOR(i,a,b) for(int i=a; i<b; i++)
#define FORR(i,a,b) for(int i=(int)b-1; i>=a; i--)

#define ALL(v) (v).begin(), (v).end()

using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;

#define DEBUG(x) cerr<<#x<<": "<<(x)<<endl
#define CHMIN(a,b) (a)=min((a),(b))
#define CHMAX(a,b) (a)=max((a),(b))

void debug_vec(vi v){
    for(int x:v){
        fprintf(stderr,"%d,",x);
    }fprintf(stderr,"\n");
}

int n,m,l;
char hand[7][25];
int typ[7];
int pls[7];

bool ctn(vi &a, vi &pat){
    REP(i,a.size())if(a[i]<pat[i])return false;
    return true;
}

ll encode(const vi &v){
    ll ret = 0;
    REP(i,l){
        ret *= 256;
        ret += v[i];
    }
    return ret;
}
vi decode(ll x){
    vi v;
    REP(i,l){
        v.push_back(x%256);
        x/=256;
    }
    reverse(ALL(v));
    return v;
}

ll fact[14];
ll comb[525][14];

int main(){
    fact[0] = 1;
    FOR(i,1,14)fact[i]=i*fact[i-1];
    REP(i,525)REP(j,14){
        if(j>i)comb[i][j]=0;
        else if(i==j || j==0)comb[i][j]=1;
        else comb[i][j]=comb[i-1][j-1] + comb[i-1][j];
    }
    while(true){
        scanf("%d%d%d",&n,&m,&l);
        if(n+m+l==0)break;
        REP(i,l){
            fill(hand[i],hand[i]+25,'\0');
            scanf("%s",hand[i]);
        }
        // to asterisk
        int a=0,b=0,c=0,d=0;
        REP(i,l){
            char x = hand[i][0];
            if(x=='*'){
                d++;
                typ[i]=3;
                pls[i]=0;
            }else if(x=='a'){
                a++;
                typ[i]=0;
                pls[i]=strlen(hand[i])-1;
            }else if(x=='b'){
                b++;
                typ[i]=1;
                pls[i]=strlen(hand[i])-1;
            }else if(x=='c'){
                c++;
                typ[i]=2;
                pls[i]=strlen(hand[i])-1;
            }
        }
        if(a==1){
            REP(i,l)if(typ[i]==0)typ[i]=3,pls[i]=0;
            a=0;
        }
        if(b==1){
            REP(i,l)if(typ[i]==1)typ[i]=3,pls[i]=0;
            b=0;
        }
        if(c==1){
            REP(i,l)if(typ[i]==2)typ[i]=3,pls[i]=0;
            c=0;
        }
        // sort
        if(a==0){
            // a<-c
            REP(i,l)if(typ[i]==2)typ[i]=0;
            a=c;c=0;
        }
        if(a==0){
            // a<-b
            REP(i,l)if(typ[i]==1)typ[i]=0;
            a=b;b=0;
        }
        if(b==0){
            // b<-c
            REP(i,l)if(typ[i]==2)typ[i]=1;
            b=c;c=0;
        }
        // REP(i,l)printf("%d %d\n",typ[i],pls[i]);
        // split
        if(a==0){
            // all asterisk
            puts("1.0000000000");
        }else if(b==0){
            // single char
            vi pat(7,0);
            int mx = 0;
            REP(i,l)if(typ[i]==0)CHMAX(mx,pls[i]);
            REP(i,l)if(typ[i]==0){
                pat[6-mx+pls[i]]++;
            }
            // REP(i,7)printf("%d ",pat[i]);puts("");
            map<vi,ll> dp[2][8][2];
            dp[0][0][0][vi(7,0)] = 1;
            int cur = 0;
            REP(t,m){
                int nxt = cur^1;
                REP(i,8)REP(j,2)dp[nxt][i][j].clear();
                REP(used,l+1)REP(flag,2)for(auto &P:dp[cur][used][flag]){
                    REP(use,n+1){
                        if(used+use>l)break;
                        vi nv(7);
                        REP(i,6)nv[i] = P.first[i+1];
                        nv[6] = use;
                        int nuse = used + use;
                        int nflag = flag || ctn(nv,pat);
                        dp[nxt][nuse][nflag][nv] += P.second * comb[n][use];
                    }
                }
                cur = nxt;
            }
            ll ans = 0;
            for(auto &P:dp[cur][l][1]){
                ans += P.second;
            }
            // DEBUG(ans);
            printf("%.10f\n",1.0*ans/comb[n*m][l]);
        }else{
            vector<vi> pats;
            REP(c,3){
                vi pat;
                REP(i,l)if(typ[i]==c){
                    while(pat.size() <= pls[i])pat.push_back(0);
                    pat[pls[i]]++;
                }
                if(pat.size()>0)pats.push_back(pat);
            }
            REP(i,l)if(typ[i]==3){
                pats.push_back(vi(1,1));
            }
            sort(ALL(pats));
            set<vector<vi>> S;
            stack<vector<vi>> T;
            do{
                S.insert(pats);
                T.push(pats);
            }while(next_permutation(ALL(pats)));
            while(T.size()){
                vector<vi> V = T.top(); T.pop();
                int nn = V.size();
                REP(i,nn-1){
                    vector<vi> NV;
                    REP(j,nn){
                        if(j==i){
                            // insert combine
                            NV.push_back(vi()); // dummy
                        }else if(j==i+1){
                            continue;
                        }else{
                            NV.push_back(V[j]);
                        }
                    }
                    vi x = V[i];
                    vi y = V[i+1];
                    int xl = x.size();
                    int yl = y.size();
                    // slide y
                    REP(j,xl+1){
                        vi z(max(xl,j+yl),0);
                        REP(k,xl)z[k]+=x[k];
                        REP(k,yl)z[j+k]+=y[k];
                        if(*max_element(ALL(z))>n)continue;
                        vector<vi> NNV = NV;
                        NNV[i] = z;
                        if(!S.count(NNV)){
                            S.insert(NNV);
                            T.push(NNV);
                        }
                    }
                    // slide x
                    FOR(j,1,yl+1){
                        vi z(max(j+xl,yl),0);
                        REP(k,xl)z[j+k]+=x[k];
                        REP(k,yl)z[k]+=y[k];
                        if(*max_element(ALL(z))>n)continue;
                        vector<vi> NNV = NV;
                        NNV[i] = z;
                        if(!S.count(NNV)){
                            S.insert(NNV);
                            T.push(NNV);
                        }
                    }
                }
            }
            ll total = comb[n*m][l];
            ll cnt = 0;
            for(vector<vi> pat:S){
                int nn = pat.size();
                // fprintf(stderr,"nn=%d\n",nn);
                ll mul = 1;
                int len = 0;
                for(vi V:pat){
                    // debug_vec(V);
                    len += V.size();
                    REP(i,V.size()){
                        mul *= comb[n][V[i]];
                        // fprintf(stderr, "(%d,%d)\n", n,V[i]);
                    }
                }
                // position: nn+1
                // num:      m-len-(nn-1)=m-len-nn+1
                if(m-len<nn-1)continue;
                // DEBUG(mul);
                // DEBUG(m-len+1);
                // DEBUG(nn);
                // DEBUG(comb[m-len+1][nn]);
                mul *= comb[m-len+1][nn];
                // DEBUG(mul);
                cnt += mul;
            }
            // DEBUG(cnt);
            // DEBUG(total);
            // if(cnt<0)return 0;
            printf("%.10f\n",1.0*cnt/total);
        }
        // }else if(c==0){
        //     // double char
        //     if(d<=2){
        //         // brute force
        //         ll total = comb[n*m][l];
        //         ll poyo = 0;
        //         unordered_set<ll> S;
        //         REP(x,m)REP(y,m)REP(z,m)REP(w,z+1){
        //             int aa[] = {x,y,z,w};
        //             vi v;
        //             int po = 0;
        //             REP(i,l){
        //                 if(typ[i]<3){
        //                     v.push_back(aa[typ[i]]+pls[i]);
        //                 }else{
        //                     v.push_back(aa[2+po]);
        //                     po++;
        //                 }
        //             }
        //             sort(ALL(v));
        //             if(v.back()>=m){
        //                 // DEBUG("!?");
        //                 continue;
        //             }
        //             int bef = -1;
        //             int cnt = 0;
        //             // ll pat = fact(l);
        //             ll pat = 1;
        //             REP(i,l){
        //                 if(v[i]==bef){
        //                     cnt++;
        //                     if(cnt>n)break;
        //                 }else{
        //                     // pat /= fact(cnt);
        //                     pat *= comb[n][cnt];
        //                     bef=v[i];
        //                     cnt=1;
        //                 }
        //             }
        //             if(cnt>n){
        //                 // DEBUG("!?");
        //                 continue;
        //             }
        //             // pat /= fact(cnt);
        //             pat *= comb[n][cnt];

        //             ll id = encode(v);
        //             if(S.count(id))continue;
        //             S.insert(id);
        //             poyo += pat;
        //         }
        //         printf("%.10f\n",1.0 * poyo / total);
        //     }else{
        //         // no brute-force
        //         int hori=0, vert=0;
        //         REP(c,2){
        //             int c0=0,c1=0;
        //             REP(i,l)if(typ[i]==c)(pls[i]==0?c0:c1)++;
        //             if(c0==2){
        //                 vert++;
        //             }else{
        //                 hori++;
        //             }
        //         }
        //         puts("not implemented");
        //     }
        // }else{
        //     // triple char
        //     // brute force
        //     ll total = comb[n*m][l];
        //     ll poyo = 0;
        //     unordered_set<ll> S;
        //     REP(x,m)REP(y,m)REP(z,m)REP(w,m){
        //         int aa[] = {x,y,z,w};
        //         vi v;
        //         REP(i,l){
        //             v.push_back(aa[typ[i]]+pls[i]);
        //         }
        //         sort(ALL(v));
        //         if(v.back()>=m){
        //             // DEBUG("!?");
        //             continue;
        //         }
        //         int bef = -1;
        //         int cnt = 0;
        //         // ll pat = fact(l);
        //         ll pat = 1;
        //         REP(i,l){
        //             if(v[i]==bef){
        //                 cnt++;
        //                 if(cnt>n)break;
        //             }else{
        //                 // pat /= fact(cnt);
        //                 pat *= comb[n][cnt];
        //                 bef=v[i];
        //                 cnt=1;
        //             }
        //         }
        //         if(cnt>n){
        //             // DEBUG("!?");
        //             continue;
        //         }
        //         // pat /= fact(cnt);
        //         pat *= comb[n][cnt];

        //         ll id = encode(v);
        //         if(S.count(id))continue;
        //         S.insert(id);
        //         poyo += pat;
        //     }
        //     printf("%.10f\n",1.0 * poyo / total);
        // }
    }
    return 0;
}