Загальний Покер
У вас є колода розміром 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}.
Не повинно бути інших символів у виході.