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 <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cstring>
#include <functional>
#include <cmath>
#include <complex>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(n);++i)
#define all(c) (c).begin(),(c).end()
#define fs first
#define sc second
#define pb push_back
#define show(x) cout << #x << " " << x << endl
typedef long long ll;
int N,M,L,w;
vector<int> cs[3];
int p3[8];
ll C[421][421];
bool acc(int id,int* mycnt){
	if(id>60) return false;
	mycnt[id]++;
	return true;
}
int main(){
	p3[0]=1;
	rep(i,7) p3[i+1]=p3[i]*3;
	rep(i,421){
		C[i][0]=C[i][i]=1;
		for(int j=1;j<min(i,8);j++) C[i][j]=C[i-1][j-1]+C[i-1][j];
	}
	while(true){
		cin>>N>>M>>L;
		if(N==0) break;
		rep(i,3) cs[i].clear();
		w=0;
		rep(i,L){
			string s;
			cin>>s;
			if(s[0]=='*') w++;
			else cs[s[0]-'a'].pb(s.size()-1);
		}
		if(cs[0].empty()&&!cs[1].empty()) swap(cs[0],cs[1]);
		if(cs[1].empty()&&!cs[2].empty()) swap(cs[1],cs[2]);
		if(cs[0].empty()&&!cs[2].empty()) swap(cs[0],cs[2]);
		int n=3;
		if(cs[2].empty()) n=2;
		if(cs[1].empty()) n=1;
		if(cs[0].empty()) n=3;
		ll ans=0;
		rep(i,p3[L-1]){
			int a[8]={},e[8]={},tmp=i,cnt[61]={};
			int gap=0,eq=0;
			rep(j,L-1){
				a[j]=tmp%3;
				tmp/=3;
				if(a[j]==2) gap++;
				if(a[j]==0) eq++;
			}
//			if(gap>=n) continue;
			rep(j,L-1){
				if(a[j]==2){
					e[j+1]=(e[j]/10+1)*10;
				}else{
					e[j+1]=e[j]+a[j];
				}
			}
			rep(j,L) cnt[e[j]]++;
			bool can=0;
			rep(j,61) if(cnt[j]>N) goto hoge;
			rep(j,L) rep(k,L) rep(h,L){
				int mycnt[61]={};
				bool ok=1;
				rep(jj,cs[0].size()) if(!acc(e[j]+cs[0][jj],mycnt)) ok=0;
				rep(kk,cs[1].size()) if(!acc(e[k]+cs[1][kk],mycnt)) ok=0;
				rep(hh,cs[2].size()) if(!acc(e[h]+cs[2][hh],mycnt)) ok=0;
				ll co=1;
				rep(p,61){
					if(cnt[p]<mycnt[p]) ok=0;
				}
				if(ok){
					can=1;
					goto hoge;
				}
			}
			hoge:
			if(can){
				ll co=1;
				rep(p,61) co*=C[N][cnt[p]];
//				printf("%d,%d,%d  ->  co=%lld\n",a[2],a[1],a[0],co);
//				show(M-(L-1-eq));
//				show(gap+1);
				if(M-(L-1-eq)<0||M-(L-1-eq)<gap+1) continue;
//				printf("%d,%d,%d  ->  narabe=%lld\n",a[0],a[1],a[2],C[M-(L-1-eq)][gap+1]);
				co*=C[M-(L-1-eq)][gap+1];
				ans+=co;
//				printf("%d,  %lld\n",i,co);
			}else{
//				printf("%d,no\n",i);
			}
		}
//		printf("ans=%lld\nC[][]=%lld\n",ans,C[N*M][L]);
		printf("%.12f\n",(double)ans/C[N*M][L]);
	}
}