006 - 一般化ポーカー

1からMのランクを持つN × M 枚のカードのデッキがある． それぞれのランクごとにN枚のカードが含まれている．

ランクmのカードのことを以下ではmと記述する．

デッキからL枚の手札をランダムに引くことができる．その手札 が与えられたパターンにマッチしているとボーナスが与えられる．パターンは， 以下のように記述される．

hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'

異なる変数の間には，表すランクについての制約はない． たとえば，'a'に対応するランクと'b'に対応するランクは同じでもよいし，異なっていてもよい．

hand_patternの例を示す．パターン

a * b a b 

は，'a'が3を, 'b'が10 を(または'a'が10を, 'b'が3を)表すとすると

3 3 10 10 9

とマッチする． 同じパターンは手札

3 3 3 3 9

ともマッチする．この時は，'a'も'b'も3を表す．パターン

a a+ a++ a+++ a++++

は手札

4 5 6 7 8

とマッチする．この場合，'a'は4になる．

デッキからランダムに取り出した手札が与えられたhand_patternにマッチする確率を求めるプログラムを作成しなさい．

入力は複数のデータセットからなる．それぞれのデータセットは以下の形式からなる．

N M L
card_pattern₁ card_pattern₂ ... card_pattern_L

最初の行は空白で区切られた三つの正の整数N, M, Lを含んでいる．Nは同ランクのカードの数, Mはランクの数，Lは手札の枚数を示す．N, M, Lは以下の制約を満たす．

1 ≤ N ≤ 7
1 ≤ M ≤ 60
1 ≤ L ≤ 7
L ≤ N × M

2行目はhand_patternを記述している．

入力の終わりは空白一つで区切られたゼロ3個からなる行によって示される．

各データセットについて，そのhand_patternに手札がマッチする確率を小数として出力せよ．

出力には10⁻⁸を超える誤差があってはならない．

それ以外の文字を含んでいてはならない．

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

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