Общий покер
У вас есть колода размером N×M карт. Каждая карта в колоде имеет ранг, который варьируется от 1 до M, и в колоде содержится N карт каждого ранга.
Мы обозначаем карту с рангом m как m.
Вы можете случайным образом вытянуть руку из L карт из колоды. Если рука соответствует заданному шаблону, вы получаете бонус. Шаблон описывается следующим образом:
hand_pattern = card_pattern1 ' ' card_pattern2 ' ' ... ' ' card_patternL
card_pattern = '*' | var_plus
var_plus = variable | var_plus '+'
variable = 'a' | 'b' | 'c'
hand_pattern
Рука соответствует hand_pattern, если каждый card_pattern в hand_pattern соответствует отдельной карте в руке.
card_pattern
Если card_pattern — это звёздочка ('*'), она соответствует любой карте. Символы 'a', 'b' и 'c' обозначают переменные, и все вхождения одной и той же переменной соответствуют картам одного и того же ранга. card_pattern с переменной, за которой следуют символы плюс ('+'), соответствует карте, чей ранг равен сумме ранга, соответствующего переменной, и количества символов плюс. Можно предположить, что, когда hand_pattern включает card_pattern с переменной и некоторым количеством символов плюс, она также включает card_patterns с этой переменной и всеми меньшими числами (включая ноль) символов плюс. Например, если 'a+++' появляется в hand_pattern, card_patterns 'a', 'a+' и 'a++' также появляются в hand_pattern.
Нет ограничений на то, какие ранги обозначают разные переменные. Например, 'a' и 'b' могут или не могут соответствовать картам одного и того же ранга.
Приведём несколько примеров hand_patterns. Шаблон
a * b a b
соответствует руке:
3 3 10 10 9
где 'a' и 'b' означают 3 и 10 (или 10 и 3), соответственно. Этот шаблон также соответствует следующей руке.
3 3 3 3 9
В этом случае и 'a', и 'b' означают 3. Шаблон
a a+ a++ a+++ a++++
соответствует следующей руке.
4 5 6 7 8
В этом случае 'a' должна означать 4.
Ваша задача — написать программу, которая вычисляет вероятность того, что рука, случайно вытянутая из колоды, соответствует заданному hand_pattern.
Входные данные
Входные данные представляют собой последовательность наборов данных. Каждый набор данных форматируется следующим образом.
N M Lcard_pattern_1 card_pattern_2 ... card_pattern_L
Первая строка состоит из трех положительных целых чисел N, M и L. N указывает количество карт каждого ранга, M указывает количество рангов, а L указывает количество карт в руке. N, M и L ограничены следующим образом.
1 ≤ N ≤ 71 ≤ M ≤ 601 ≤ L ≤ 7L ≤ N×M
Вторая строка описывает hand_pattern.
Конец ввода обозначается строкой, содержащей три нуля, разделенные одним пробелом.
Выходные данные
Для каждого набора данных выведите строку, содержащую десятичную дробь, которая означает вероятность того, что рука соответствует hand_pattern.
Вывод не должен содержать ошибку больше 10^{−8}.
Не должно быть других символов в выводе.