Space Poker 3
Space poker. A legendary game, first version of which was introduced as far as in year 1284 of Alien era. Even nowadays its rules are known only to small group of professional players. Fortunately, the developers of the first program in the world playing space poker asked for your help.
There are N extraterrestial players in space poker. At the beginning of the round, each player gets M cards (we call them hole cards). Players don't know hole cards of their opponents. Then K community cards are consecutively dealt face-up. So, community cards are known to all players. Player's hand consists of his hole cards and all community cards — M+K cards in total. There are no suits, cards differ only in their values. There are 13 different values: "2", "3", "4", …, "9", "T", "J", "Q", "K" and "A". The card deck is infinite, and the probability of the event that the next card will have a given value is equal to 1/13. The combinations in space poker are represented in the form: (v_1, …, v_L), where L is the number of different values in the combination. The hand satisfies the combination (v_1, …, v_L) in case it contains v_1cards of one value, v_2 cards of another value, …, v_L cards of L-th value. For example, combination (2, 2) is satisfied by hands "2JA2A" and "22233". Combination (2, 3) is satisfied by hand "KQKQKQ" but is not satisfied by hand "AAAAAA". All combinations have different strength. The winner of the round is a player whose hand satisfies the combination of the maximal strength among all combinations in hands of all players. If there is more than one such player, the round ends in a draw.
Suppose you know the hole cards of the first player and partly dealt community cards. Calculate the probability the first player will be the only winner of this round.
Input
The first line contains integers N, M and K separated by spaces (2 ≤ N, M ≤ 10; 1 ≤ K ≤ 5). The second line contains M symbols — hole cards of the first player. The third line contains at most K symbols — dealt community cards. The fourth line contains integer C — the number of combinations in space poker (1 ≤ C ≤ 100). The following C lines contain combinations in order of increasing strength. Each description has the form L v_1 v_2 … v_L. L and v_i are positive integers, sum of all v_i doesn't exceed M+K.
Output
Output the probability of winning for the first player with absolute error not exceeding 10^{−5}.