Generic Poker
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 Lcard_pattern_1 card_pattern_2 ... card_pattern_L
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 ≤ 71 ≤ M ≤ 601 ≤ L ≤ 7L ≤ 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 thehand_pattern.
The output should not contain an error greater than 10^{−8}.
No other characters should be contained in the output.