Generic Poker

時間制限 : 8 sec, メモリ制限 : 65536 KB
英語版はこちら

一般化ポーカー

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'

hand_pattern
hand_pattern中の各card_patternがそれぞれ手札中の異なるカードにマッチすれば, その手札はhand_patternにマッチする.
card_pattern
card_patternがアステリスク('*')の時はどのカードにもマッチする. 文字'a', 'b', 'c'は変数を表し,同じ変数は同じランクのカードとマッチする. 変数の後に1個以上のプラス('+')を続けたパターンは,変数に対応するランクに'+'の個数を足して得られるラ ンクのカードにマッチする. 変数の後に'+'をいくつか続けたパターンがhand_patternに含まれる時は, 同じ変数の後に'+'をより少ない数(ゼロを含む)続けたパターンがすべてhand_patternに含まれると 仮定してよい.たとえば,'a+++'がhand_patternに現れる時は,'a', 'a+', 'a++' が hand_patternに現れる.

異なる変数の間には,表すランクについての制約はない. たとえば,'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にマッチする確率を求めるプログラムを作成しなさい.

Input

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

N M L
card_pattern1 card_pattern2 ... card_patternL

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

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

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

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

Output

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

出力には10−8を超える誤差があってはならない.

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

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

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2012-07-6
http://www.cs.titech.ac.jp/icpc2012/