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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{

	char ch;
	int maximum,count_table[7];
};

int table[7],work[7];
int N,M,L;
int check_index;
ll dp[8][61];
double nCm[421][8];
char pattern[7][10];
char check_table[5040][7];
vector<vector<Info>> SECTION;
Info info[7],calc_info[7],work_info[7],section[7];


//連続した数字の塊【区間】を0～M-1に当てはめる【最大L個】
ll dfs(int section_index,int num_section,int num_index){

	if(num_index == M){

		if(section_index < num_section){ //当てはめをしていない区間あり

			return 0;
		}else{

			return 1;
		}
	}

	if(dp[section_index][num_index] != -1){

		return dp[section_index][num_index];
	}

	ll ret = 0;

	//割り当てない
	ret += dfs(section_index,num_section,num_index+1);

	//割り当てる
	if(section_index < num_section){

		int tail = num_index+section[section_index].maximum;
		if(tail <= M-1){

			//★重複計上を防ぐため、区間と区間の間には少なくとも1つの空白を設ける★
			ret += dfs(section_index+1,num_section,min(M,tail+2));
		}
	}

	return dp[section_index][num_index] = ret;
}

void makeSection(int section_index,int num_info,int work_index){

	if(section_index == num_info){ //区間作成完了

		//既存区間と重複していないか調べる
		bool FLG = false;

		for(int i = 0; i < SECTION.size(); i++){
			FLG = true;
			if(SECTION[i].size() != work_index){ //区間の数が異なるならOK
				FLG = false;
				continue;
			}
			for(int k = 0; k < SECTION[i].size(); k++){
				if(SECTION[i][k].maximum != work_info[k].maximum){ //ある区間の長さが異なるならOK

					FLG = false;
					break;
				}
				for(int p = 0; p <= SECTION[i][k].maximum; p++){
					if(SECTION[i][k].count_table[p] != work_info[k].count_table[p]){ //ある数字の数が異なるならOK

						FLG = false;
						break;
					}
				}
				if(!FLG)break;
			}
			if(FLG)break;
		}

		if(FLG)return;

		vector<Info> vec;

		for(int i = 0; i < work_index; i++){

			vec.push_back(work_info[i]);
		}

		SECTION.emplace_back(vec);

		return;
	}

	//既存の区間と重なりを持つ場合
	for(int i = 0; i < work_index; i++){
		for(int merge_head = 0; merge_head <= work_info[i].maximum+1; merge_head++){

			if(merge_head+calc_info[section_index].maximum >= min(L,M))continue;

			//数字の個数がNを越えないか調べる
			bool FLG = true;
			for(int k = 0; merge_head+k <= work_info[i].maximum && k <= calc_info[section_index].maximum; k++){
				if(work_info[i].count_table[merge_head+k]+calc_info[section_index].count_table[k] > N){

					FLG = false;
					break;
				}
			}

			if(!FLG)continue;

			int pre_max = work_info[i].maximum;

			for(int k = 0; k <= calc_info[section_index].maximum; k++){
				work_info[i].count_table[merge_head+k] += calc_info[section_index].count_table[k];
				work_info[i].maximum = max(work_info[i].maximum,merge_head+k);
			}

			makeSection(section_index+1,num_info,work_index);

			//元に戻す
			for(int k = 0; k <= calc_info[section_index].maximum; k++){
				work_info[i].count_table[merge_head+k] -= calc_info[section_index].count_table[k];
			}
			work_info[i].maximum = pre_max;
		}
	}


	//新しい区間とする場合
	work_info[work_index] = calc_info[section_index];
	makeSection(section_index+1,num_info,work_index+1);
}


void func(){

	for(int i = 0; i < L; i++){

		scanf("%s",pattern[i]);
	}
	printf("\n");

	SECTION.clear();

	double num_all = nCm[N*M][L];

	/*patternに該当する場合の数を計上する*/

	//pattern情報を調べる
	int num_info = 0;
	for(int i = 0; i < 7; i++){
		for(int k = 0; k < 7; k++){
			info[i].count_table[k] = 0;
		}
	}

	for(int i = 0; i < L; i++){

		if(pattern[i][0] == '*'){ //独立させる

			info[num_info].ch = '*';
			info[num_info].maximum = 0;
			info[num_info].count_table[0] = 1;

			num_info++;

		}else{

			int index = -1;

			for(int k = 0; k < num_info; k++){

				if(info[k].ch == pattern[i][0]){

					index = k;
					break;
				}
			}

			if(index == -1){

				info[num_info].ch = pattern[i][0];
				info[num_info].maximum = 0;
				index = num_info;
				num_info++;
			}

			int num_plus = 0;

			for(int k = 1; pattern[i][k] == '+'; k++,num_plus++);

			info[index].count_table[num_plus] += 1; //a a a++ a++ a+++ 等
			info[index].maximum = max(info[index].maximum,num_plus);
		}
	}

	//patternにマッチする場合を数え上げる
	//★★★★異なる変数の間には、表すランクについての制約はない★★★★

	//区間の集合を作成する
	int perm_table[7];
	for(int i = 0; i < num_info; i++){
		perm_table[i] = i;
	}

	check_index = 0;

	do{

		for(int i = 0; i < num_info; i++){ //infoを固定すると計上漏れが発生する

			calc_info[i] = info[perm_table[i]];
		}

		bool FLG = false;

		//既に処理していないか調べる
		for(int i = 0; i < check_index; i++){
			FLG = true;
			for(int k = 0; k < num_info; k++){
				if(check_table[i][k] != calc_info[k].ch){
					FLG = false;
					break;
				}
			}
			if(FLG)break;
		}

		if(FLG)continue;

		for(int i = 0; i < num_info; i++){

			check_table[check_index][i] = calc_info[i].ch;
		}

		check_index++;

		makeSection(0,num_info,0);

	}while(next_permutation(perm_table,perm_table+num_info));

	//区間の集合を走査し、その割り当て方ごとに、場合の数を計上する
	double num_pattern = 0;

	for(int i = 0; i < SECTION.size(); i++){

		int num_section = SECTION[i].size();

		for(int k = 0; k < num_section; k++){

			section[k] = SECTION[i][k];		}

		double base = 1;
		for(int k = 0; k < num_section; k++){
			for(int p = 0; p <= SECTION[i][k].maximum; p++){

				base *= nCm[N][SECTION[i][k].count_table[p]];
			}
		}

		for(int a = 0; a <= num_section; a++){
			for(int b = 0; b <= M; b++){
				dp[a][b] = -1;
			}
		}

		num_pattern += base*dfs(0,num_section,0); //数字の選び方*区間の割り当て方を加算
	}

	printf("%.10lf\n",num_pattern/num_all);
}

void makeTable(){

	nCm[0][0] = 1;
	for(ll n = 1; n <= 420; n++) {
		for (int m = 0; m <= 7; m++) {
			if(m > 0){
				nCm[n][m] = nCm[n-1][m]+nCm[n-1][m-1];
			}else{ //m == 0
				nCm[n][m] = 1;
			}
		}
	}
}

int main(){

	makeTable();

	while(true){

		scanf("%d %d %d",&N,&M,&L);
		if(N == 0 && M == 0 && L == 0)break;

		func();
	}

	return 0;
}