Generic Poker

ID: 3033

Type: Default

8000ms

134MiB

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 L card_pattern1 card_pattern2 ... card_patternL

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.

Output

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.

Sample Input

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

Output for the Sample Input

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

Example

Input

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

Output

inputFormat

Input

The input is a sequence of datasets. Each dataset is formatted as follows.

N M L card_pattern1 card_pattern2 ... card_patternL

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.

outputFormat

Output

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.

Sample Input

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

Output for the Sample Input

Example

Input

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

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

</p>

#D3657. Generic Poker

Generic Poker

Generic Poker

inputFormat

outputFormat

样例

Status

Support

#D3657. Generic Poker

Generic Poker

Generic Poker

inputFormat

outputFormat

样例

Status

Support

Don't have an account?

SIGN IN