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>

#ifdef LOCAL
#include "dump.hpp"
#else
#define dump(...)
#endif

using namespace std;

constexpr int MAX_N = 7;
constexpr int MAX_M = 60;
constexpr int MAX_L = 7;

int N, M, L;

map<char, int> c;
int kind[MAX_L];
int num[MAX_L];
int hand[MAX_L];

long long memo[MAX_N * MAX_M + 1][MAX_L + 1];
long long combination(int n, int k) {
	if(k == 0 || n == k) return 1;
	auto &res = memo[n][k];
	if(res) return res;
	return res = combination(n - 1, k - 1) + combination(n - 1, k);
}

bool match() {
	vector<int> value(c.size());
	vector<int> card(hand, hand + L);

	do {
		fill(begin(value), end(value), -1);
		for(int i = 0; i < L; ++i) {
			if(kind[i] == -1) continue;

			if(value[kind[i]] == -1) {
				if(card[i] <= num[i]) goto fail;
				value[kind[i]] = card[i] - num[i];
			}
			else {
				if(value[kind[i]] != card[i] - num[i]) goto fail;
			}
		}
		return true;

	fail:;
	} while(next_permutation(begin(card), end(card)));

	return false;
}

long long calc() {
	if(!match()) return 0;

	long long res = 1;
	map<int, int> cnt;
	for(int i = 0; i < L; ++i) {
		++cnt[hand[i]];
	}

	for(const auto &e : cnt) {
		res *= combination(N, e.second);
	}

	int select = 1;
	for(int i = 1; i < L; ++i) {
		if(hand[i - 1] + 1 <  hand[i]) ++select;
	}

	res *= combination(M - (hand[L - 1] - select), select);
	return res;
}

long long dfs(int idx, int len) {
	if(idx == L) return calc();

	long long res = 0;
	for(int i = 0; i < 3; ++i) {
		if(i == 0 && len == N) continue;
		if(hand[0] + M <= hand[idx - 1] + i) break;
		hand[idx] = hand[idx - 1] + i;
		res += dfs(idx + 1, (i ? 1 : len + 1));
	}
	return res;
}

int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cout.setf(ios::fixed);
	//cout.precision(10);
	cout.precision(9);

	while(cin >> N >> M >> L && N) {
		c.clear();

		for(int i = 0; i < L; ++i) {
			string pattern;
			cin >> pattern;

			if(pattern == "*") {
				kind[i] = -1;
			}
			else {
				if(!c.count(pattern[0])) c.insert({pattern[0], c.size()});
				kind[i] = c[pattern[0]];
				num[i] = pattern.size() - 1;
			}
		}

		dump(c);
		hand[0] = 1;
		const auto ans = (long double)dfs(1, 1) / combination(N * M, L);
		cout << ans << endl;
	}

	return EXIT_SUCCESS;
}