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 JAVA):

Solution:
import java.util.Arrays;
import java.util.Scanner;
import java.util.concurrent.SynchronousQueue;

class Main {
	public static void main(String[] args) {
		new Main().run();
	}

	int n, m, l;
	String[] s;
	int[][] p;
	long[] p3 = new long[10];
	long[][] c = new long[1000][10];

	void run() {
		{
			p3[0] = 1;
			for (int i = 1; i < p3.length; ++i) {
				p3[i] = p3[i - 1] * 3;
			}
			c[0][0] = 1;
			for (int i = 1; i < c.length; ++i) {
				for (int j = 0; j < 10; ++j) {
					c[i][j] = c[i - 1][j] + (j > 0 ? c[i - 1][j - 1] : 0);
				}
			}
		}
		Scanner sc = new Scanner(System.in);
		while (true) {
			System.gc();
			n = sc.nextInt();
			m = sc.nextInt();
			l = sc.nextInt();
			if (n == 0 && m == 0 && l == 0)
				break;
			s = new String[l];
			p = new int[3][l];
			for (int i = 0; i < l; ++i) {
				s[i] = sc.next();
				if (s[i].equals("*"))
					continue;
				++p[s[i].charAt(0) - 'a'][s[i].length() - 1];
			}
			solve();
		}
	}

	void solve() {
		long tot = 0;
		for (int S = 1; S < p3[l]; S += 3) {
			int[] a = new int[l];
			for (int i = 0; i < l; i++) {
				a[i] = (int) ((S / p3[i]) % 3);
			}
			if (check(a)) {
				long comb = 1;
				int[] cnt = cnt(arr(a));
				for (int v : cnt) {
					comb *= c[n][v];
				}
				int wall = 1;
				int res = m;
				for (int v : a) {
					if (v == 2) {
						++wall;
						res -= 2;
					} else if (v == 1) {
						res -= 1;
					}
				}
				comb *= c[res + wall][wall];
				tot += comb;
			}
		}
		System.out.printf("%.20f\n", (double) tot / c[m * n][l]);

	}

	boolean check(int[] a) {
		int[] arr = arr(a);
		if (arr[arr.length - 1] > m)
			return false;
		int[] cnt = cnt(arr);
		if (cnt.length > 20) {
			throw new AssertionError();
		}
		cnt = Arrays.copyOf(cnt, 40);
		for (int x = 0; x < arr.length; ++x) {
			for (int y = 0; y < arr.length; ++y) {
				for (int z = 0; z < arr.length; ++z) {
					// cnt[x]???a,cnt[y]???b,cnt[z]???c?????¨????????????
					int[] cnt2 = new int[40];
					for (int shift = 0; shift < l; ++shift) {
						cnt2[arr[x] + shift] += p[0][shift];
						cnt2[arr[y] + shift] += p[1][shift];
						cnt2[arr[z] + shift] += p[2][shift];
					}
					boolean f = true;
					for (int i = 0; i < cnt2.length; ++i) {
						f &= (cnt[i] >= cnt2[i]);
					}
					if (f)
						return true;
				}
			}
		}
		return false;
	}

	int[] arr(int[] a) {
		int[] seq = new int[l];
		seq[0] = a[0];// =1
		for (int i = 1; i < a.length; ++i) {
			seq[i] = seq[i - 1] + a[i];
		}
		return seq;
	}

	int[] cnt(int[] arr) {
		int[] cnt = new int[arr[arr.length - 1] + 1];
		for (int v : arr) {
			++cnt[v];
		}
		return cnt;
	}

	void tr(Object... objects) {
		System.out.println(Arrays.deepToString(objects));
	}
}