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_pattern_{1}' ' card_pattern_{2}' ' ... ' ' card_pattern_{L}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 bmatches the hand:

3 3 10 10 9with '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 9In 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 8In 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.

NML

card_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≤ 7

1 ≤M≤ 60

1 ≤L≤ 7

L≤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 the hand_pattern.

The output should not contain an error greater than 10^{−8}.

No other characters should be contained in the output.

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

Source: ACM International Collegiate Programming Contest
, Japan Domestic Contest, Tokyo, Japan, 2012-07-6

http://www.cs.titech.ac.jp/icpc2012/

http://www.cs.titech.ac.jp/icpc2012/