Космический покер 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_1v_2 … v_L. Числа L и v_i положительны, сумма всех v_i не превышает M+K.
Выходные данные
Выведите вероятность победы первого игрока с точностью не менее 10^{−5}.