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
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
matches the hand:
with 'a's and 'b's meaning 3 and 10 (or 10 and 3), respectively. This pattern also matches the following hand.
In this case, both 'a's and 'b's mean 3. The pattern
matches the following hand.
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.
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.
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.