Космічний покер 3
Космічний покер. Легендарна гра, перша версія якої з'явилась ще у далекому 1284 році Чужої ери. До цього часу її правила відомі лише вузькому колу професійних гравців. Протк Вам повезло — розробники першої у світі програми, яка грає у космічний покер, звернулись до Вас за допомогою.
У космічний покер грає N інопланетян. На початку раунда кожному з гравців роздають по M карт (назвемо їх особистими). Особисті карти гравця невідомі його суперникам. Потім на стіл по черзі викладаються K спільних карт. Спільні карти кладуть рубашкою донизу, тому вони видні усім гравцям. Рука гравця складається з його особистих та спільних карт — усього M+K карт. Мастей немає, карти розрізняються лишь номіналом. Усього є 13 різних номіналів: "2", "3", "4", …, "9", "T", "J", "Q", "K" та "A". Грають нескінченною колодою, у якій ймовірність того, що чергова карта буде мати заданий номінал, дорівнює 1/13. Комбінації у космічному покері мають вигляд (v_1, …, v_L), де L — кількість різних номіналів у комбінації. Рука гравця задовольняє комбінації (v_1, …, v_L), якщо містить v_1 карт першого номіналу, v_2 карт другого номіналу, …, v_L карт L-го номіналу. Наприклда, комбінації (2, 2) задовольняють руки "2JA2A" та "22233". Комбінації (2, 3) задовольняє рука "KQKQKQ", але не задовольняє рука "AAAAAA". Усі комбінації мають різну вартість. У раунді перемагає гравець, рука якого містить комбінацію найбільшої вартості серед усіх комбінацій на руках усіх гравців. Якщо таких гравців декілька, оголошується нічия.
Знаючи особисті карти першого гравця та частково відкриті спільні карти, порахуйте ймовірність того, що цей гравець виявитьсяя єдиним переможцем раунда.
Вхідні дані
У першому рядку через пропуск записано числа N, M та K (2 ≤ N, M ≤ 10, 1 ≤ K ≤ 5). У другому рядку записано M символів — особисті карти першого гравця. У третьому рядку записано не більше K символів — відкриті спільні карти. У четвертому рядку записано число C — кількість існуючих у космічному покері комбінацій (1 ≤ C ≤ 100). Далі у C рядках перераховано комбінації у порядку зростання вартості. Кожна з них має вигляд L v_1 v_2 … v_L. Числа L та v_i додатні, сума усіх v_i не перевищує M+K.
Вихідні дані
Виведіть ймовірність перемоги першого гравця з точністю не менше 10^{−5}.