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<cstdio>
#include<vector>
#include<string>
#include<iomanip>
#include<iostream>
#include<algorithm>

using namespace std;

vector<int> a[3];

void parse(string str){
	if(str[0]=='*'){
//		star++;
	}else{
		int cnt=str.size()-1;
		int id=str[0]-'a';
		a[id].push_back(cnt);
	}
}

int dif[7];
int val[7];
int L;

bool used[7];

int N,M;

bool dfs(int id){
	if(id==3){
		return true;
	}
	for(int i=0;i<L;i++){
		vector<int> tmp;
		int k=0;
		int x=val[i];
		for(int j=i;j<L;j++){
			if(k==a[id].size()) break;
			if(used[j]) continue;
			if(val[j]==x+a[id][k]){
				tmp.push_back(j);
				k++;
			}
		}
		if(k!=a[id].size()){
			continue;
		}
		for(int j=0;j<tmp.size();j++){
			used[tmp[j]]=true;
		}
		bool flg=dfs(id+1);
		if(flg) return true;
		for(int j=0;j<tmp.size();j++){
			used[tmp[j]]=false;
		}
	}
	return false;
}

bool check(){
	for(int i=0;i+N<L;i++){
		if(val[i]==val[i+N]) return false;
	}
	if(val[L-1]-val[0]>M-1) return false;
	for(int i=0;i<L;i++) used[i]=false;
//	printf("dfs\n");
	bool flg=dfs(0);
	return flg;
}

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

double res;

void calc(){
//	printf("calc ");
	val[0]=0;
	for(int i=1;i<L;i++){
		val[i]=val[i-1]+dif[i-1];
	}
//	for(int i=0;i<L;i++) printf("%d ",val[i]);
//	printf("\n");
	bool flg=check();
	if(flg==false) return;
	double all=C(N*M,L);
	double cur=0;
	int cnt=0;
	for(int i=0;i<L-1;i++) if(dif[i]==2) cnt++;
	int sum=0;
	for(int i=0;i<L-1;i++) if(dif[i]!=2) sum+=dif[i];
//	printf("%d %d\n",cnt,sum);
	if(cnt==0){
		cur=M-sum;
	}else{
		for(int i=cnt*2;i<=M-1-sum;i++){
			double ad=C(i-cnt-1,cnt-1);
			ad*=(M-sum-i);
			cur+=ad;
//			printf("+=(%d %d)=%f\n",i-cnt-1,cnt-1,C(i-cnt-1,cnt-1));
		}
	}
	for(int i=0;i<L;i++){
		if(i!=0&&dif[i-1]==0) continue;
		int num=0;
		for(int j=i;j<L;j++){
			if(val[i]==val[j]) num++;
			else break;
		}
		cur*=C(N,num);
	}
//	printf("res+=%f\n",cur/all);
	res+=cur/all;
}

void dfs2(int i){
	if(i==L-1){
		calc();
		return;
	}
	for(int j=0;j<=2;j++){
		dif[i]=j;
		dfs2(i+1);
	}
}

double solve(){
	if(L==1) return 1;
	res=0;
	dfs2(0);
	return res;
}

void init(){
	for(int i=0;i<3;i++) a[i].clear();
}

int main(){
	int T=1;
	while(true){
		init();
		cin>>N>>M>>L;
		if(N==0) break;
		for(int i=0;i<L;i++){
			string str;
			cin>>str;
			parse(str);
		}
		for(int i=0;i<3;i++) sort(a[i].begin(),a[i].end());
//		for(int i=0;i<3;i++){
//			for(int j=0;j<a[i].size();j++) printf("%d ",a[i][j]);
//			printf("\n");
//		}
		double ans=solve();
	//	cout<<setprecision(9)<<ans<<"\n";
	//	printf("case %d %.9f\n",T,ans);
		printf("%.9f\n",ans);
		T++;
//		if(T==2) break;
	}
	return 0;
}