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 <iostream>
#include <cstdio>
#include <cassert>
#include <cstring>
#include <vector>
#include <valarray>
#include <array>
#include <queue>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <complex>
#include <random>

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

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

using Q = vector<vector<int>>;

vector<Q> ty[8];



int n, m, l;
P pat[7];


int buf[66];

bool match2(int a, int b, int c) {
    int d[3] = {a, b, c};
    static int bu2[66];
    copy_n(buf, 66, bu2);
    for (int i = 0; i < l; i++) {
        if (pat[i].first == -1) continue;
        int u = d[pat[i].first] + pat[i].second;
        if (bu2[u] == 0) return false;
        bu2[u]--;
    }
    return true;
}

int co;
bool match() {
    for (int a = 0; a < co; a++) {
        for (int b = 0; b < co; b++) {
            for (int c = 0; c < co; c++) {
                if (match2(a, b, c)) return true;
            }
        }
    }
    return false;
}

double calc() {
    double sm = 0;
    for (auto t: ty[l]) {
        // printf("pattern:\n");
        // for (auto v: t) {
        //     for (auto d: v) {
        //         printf("%d ", d);
        //     }
        //     printf("\n");
        // }
        // printf("patend\n");
        fill_n(buf, 66, 0);
        co = 0;
        int vs = 0;
        for (auto v: t) {
            vs += (int)v.size();
            for (auto d: v) {
                buf[co++] = d;
            }
            co++;
        }
        co--;
//        printf("patco: %d m: %d\n", co, m);
        if (m < co) continue;
        if (!match()) continue;
//        printf("matched!\n");
        double re = 1.0;
        for (int i = 0; i < m; i++) {
            re *= comb(n, buf[i]);
        }
        re *= comb(m+1 - vs, t.size());
        sm += re;
    }
    return sm / comb(n*m, l);
}

bool solve() {
    cin >> n >> m >> l;
    if (n == 0) return false;
    for (int i = 0; i < l; i++) {
        string s;
        cin >> s;
        if (s[0] == '*') {
            pat[i] = P(-1, 0);
        } else {
            pat[i].first = s[0] - 'a';
            pat[i].second = s.size() - 1;
        }
//        printf("te %d %d\n", pat[i].first, pat[i].second);
    }
    printf("%.20lf\n", calc());
    return true;
}


Q base[8];

int main() {
    base[0].push_back(vector<int>());
    for (int i = 1; i <= 7; i++) {
        for (int k = 1; k <= i; k++) {
            for (auto v: base[i-k]) {
                v.push_back(k);
                base[i].push_back(v);
            }
        }
    }

    ty[0].push_back(Q());
    for (int i = 1; i <= 7; i++) {
        for (int k = 1; k <= i; k++) {
            for (auto q: ty[i-k]) {
                for (auto b: base[k]) {
                    auto qq = q;
                    qq.push_back(b);
                    ty[i].push_back(qq);
                }
            }
        }
//        printf("%lu\n", ty[i].size());
    } 

    while (solve()) {}
    return 0;
}