Задачи
Generic Poker
Generic Poker
You have a deck of \textbf{N}×\textbf{M} cards. Each card in the deck has a rank. The range of ranks is \textbf{1} through \textbf{M}, and the deck includes \textbf{N} cards of each rank.
We denote a card with rank \textbf{m} by \textbf{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.
\begin{verbatim}
hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL\end{verbatim}\begin{verbatim}
card_pattern = '*' | var_plus\end{verbatim}\begin{verbatim}
var_plus = variable | var_plus '+'\end{verbatim}\begin{verbatim}
variable = 'a' | 'b' | 'c'\end{verbatim}\textbf{hand_pattern}
A hand matches the \textbf{hand_pattern} if each \textbf{card_pattern} in the \textbf{hand_patter}n matches with a distinct card in the hand.
\textbf{card_pattern}
If the \textbf{card_pattern} is an asterisk ('\textbf{*}'), it matches any card. Characters '\textbf{a}', '\textbf{b}', and '\textbf{c}' denote variables and all the occurrences of the same variable match cards of the same rank. A \textbf{card_pattern} with a variable followed by plus ('\textbf{+}') 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 \textbf{hand_pattern} includes a card_pattern with a variable followed by some number of plus characters, it also includes \textbf{card_patterns} with that variable and all smaller numbers (including zero) of plus characters. For example, if '\textbf{a+++}' appears in a \textbf{hand_pattern}, \textbf{card_patterns} '\textbf{a}', '\textbf{a+}', and '\textbf{a++}' also appear in the \textbf{hand_pattern}.
There is no restriction on which ranks different variables mean. For example, '\textbf{a}' and '\textbf{b}' may or may not match cards of the same rank.
We show some example \textbf{hand_patterns}. The pattern
\begin{verbatim}
a * b a b \end{verbatim}matches the hand:
\begin{verbatim}
3 3 10 10 9\end{verbatim}with '\textbf{a}'s and '\textbf{b}'s meaning \textbf{3} and \textbf{10} (or \textbf{10} and \textbf{3}), respectively. This pattern also matches the following hand.
\begin{verbatim}
3 3 3 3 9\end{verbatim}In this case, both '\textbf{a}'s and '\textbf{b}'s mean \textbf{3}. The pattern
\begin{verbatim}
a a+ a++ a+++ a++++\end{verbatim}matches the following hand.
\begin{verbatim}
4 5 6 7 8\end{verbatim}In this case, '\textbf{a}' should mean \textbf{4}.
Your mission is to write a program that computes the probability that a hand randomly drawn from the deck matches the given \textbf{hand_pattern}.
\InputFile
The input is a sequence of datasets. Each dataset is formatted as follows.
\textbf{N M Lcard_pattern_1 card_pattern_2 ... card_pattern_L}
The first line consists of three positive integers \textbf{N}, \textbf{M}, and \textbf{L}. \textbf{N} indicates the number of cards in each rank, \textbf{M} indicates the number of ranks, and \textbf{L} indicates the number of cards in a hand. \textbf{N}, \textbf{M}, and \textbf{L} are constrained as follows.
\textbf{1} ≤ \textbf{N} ≤ \textbf{71} ≤ \textbf{M} ≤ \textbf{601} ≤ \textbf{L} ≤ \textbf{7L} ≤ \textbf{N}×\textbf{M}
The second line describes a \textbf{hand_pattern}.
The end of the input is indicated by a line containing three zeros separated by a single space.
\OutputFile
For each dataset, output a line containing a decimal fraction which means the probability of a hand matching the\textbf{hand_pattern}.
The output should not contain an error greater than \textbf{10^\{−8\}}.
No other characters should be contained in the output.
Входные данные #1
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
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