Generic Poker

Time limit1sMemory limit128 MB

Summary

Count hands of L cards (ranks 1 to M, N copies each) that match a pattern of wildcards and variables shifted by pluses, then print the probability as an irreducible fraction.

Level: Hard8 of 10
Topics: Combinatorics, Brute force, Math, Implementation
Solved: No attempts yet

Problem

There is a deck of $N \times M$ cards. Each card has a rank, an integer from $1$ to $M$ , and the deck contains exactly $N$ cards of each rank. Here a card of rank $m$ is written simply as $m$ .

You draw a hand of $L$ cards uniformly at random from the deck. If the drawn hand matches the given pattern, a bonus is rewarded. A pattern is described by the following grammar.

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 the cards of the hand can be assigned one-to-one to the card_patterns so that every card_pattern matches the distinct card assigned to it.
card_pattern
- If the card_pattern is an asterisk *, it matches any card.
- The letters a, b, and c are variables, and all occurrences of the same variable must match cards of the same rank. A variable followed by + characters matches a card whose rank is (the rank assigned to that variable) + (the number of + characters).
- If a card_pattern with a variable followed by $k$ plus characters appears, you may assume every card_pattern with that variable and $0$ through $k-1$ plus characters also appears. For example, if a+++ appears, then a, a+, and a++ appear too.

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

Here are some examples. The pattern

a * b a b

matches the hand below, with a and b meaning $3$ and $10$ (or $10$ and $3$ ).

3 3 10 10 9

The same pattern also matches the following hand, where both a and b mean $3$ .

3 3 3 3 9

The pattern

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

matches the following hand, where a means $4$ .

4 5 6 7 8

Write a program that, for a given hand_pattern, computes the probability that a hand drawn at random from the deck matches the pattern.

Input

The input is a sequence of datasets. Each dataset has the following format.

N M L
card_pattern1 card_pattern2 ... card_patternL

The first line contains 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. They satisfy the following constraints.

$1 \le N \le 7$
$1 \le M \le 60$
$1 \le L \le 7$
$L \le N \times M$

The second line contains a hand_pattern consisting of $L$ card_patterns separated by single spaces.

The end of the input is indicated by a line containing three zeros separated by single spaces (0 0 0). This line is not processed.

Output

For each dataset, output on its own line the probability that the hand matches the hand_pattern as an irreducible fraction $p/q$ , where $q \ge 1$ and $\gcd(p, q) = 1$ . Print 0/1 when the probability is $0$ and 1/1 when it is $1$ . Each line must contain nothing but this fraction.

Examples5

Example 1

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

Expected output

1/1
37/42
1/1
1/1
1/1
1/3
2/5
4/33
2053/4165
41/833
19/833
192/54145
1/1
6/4165
1/4165
48899491/164771826258
1/1
2470629/24166534517840
0/1

Example 2
Input
```
2 2 2
a a
0 0 0
```
Expected output
```
1/3
```
Example 3
Input
```
1 1 1
a
0 0 0
```
Expected output
```
1/1
```
Example 4
Input
```
3 3 4
a+ * a *
0 0 0
```
Expected output
```
37/42
```
Example 5
Input
```
2 6 6
a a+ a++ b b+ b++
0 0 0
```
Expected output
```
4/33
```