Generic Poker#3771

Generic Poker

30 seconds

64 megabytes

Very hard

You have a deck of $N \times M$ N \times 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$ as $m$ .

You can draw a hand of $L$ cards at random from the deck. If the hand matches the given pattern, a 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'

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 a card_pattern is an asterisk ('*'), it matches any card. Characters 'a', 'b', and 'c' denote variables, and all occurrences of the same variable must match cards of the same rank. A card_pattern with a variable followed by one or more 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 all card_patterns with that variable and all smaller numbers (including zero) of plus characters. For example, if 'a+++' appears in a hand_pattern, the card_patterns 'a', 'a+', and 'a++' also appear in the hand_pattern.

There is no restriction on which ranks different variables refer to. For example, 'a' and 'b' may or may not match cards of the same rank.

Here are some example hand_patterns. The pattern

a * b a b

matches the hand:

3 3 10 10 9

with 'a' and 'b' denoting $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' and 'b' denote $3$ . The pattern

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

matches the following hand:

4 5 6 7 8

In this case, 'a' should denote $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$ $c a r d_p a tt er n_{1}$ card\_pattern_1 $c a r d_p a tt er n_{2}$ card\_pattern_2 ... $c a r d_p a tt er n_{L}$ card\_pattern_L

The first line consists of three positive integers $N$ , $M$ , and $L$ . $N$ is the number of cards of each rank, $M$ is the number of ranks, and $L$ is the number of cards in a hand. The constraints are

1 \leq N \leq 71 1 \leq M \leq 60 1 \leq L \leq 7 L \leq N \times M

1 \le N \le 71 \\ 1 \le M \le 60 \\ 1 \le L \le 7 \\ L \le N \times 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 is the probability that a hand matches the hand_pattern.

The output should not have an error greater than $1 0^{- 8}$ 10^{-8}.

No other characters should appear in the output.

Examples

Example 1