Дельфины
Весна… Крилики радуются солнышку, небо стало добрым и мягким, появились первые цветочки, дельфины прилетели из тёплых краёв.
Действительно! Дельфины - главный символ весны для криликов. Ведь они так красиво поют, летают, кружатся. Такое поведение дельфинов приносит радость и улыбки почти всем, почти… Учёным криликам из Института контроля популяции дельфинов в верхушках деревьев Криляндии радостная пора приносит уймй работы. Им нужно контролировать целые стаи дельфинов. Но они не расстраиваются, потому что нашли на кого повесить самую нудную работу - разработку алгоритма для предсказания популяции дельфинов в верхушках деревьев.
Итак, нужно написать программу, которая определяет вероятные позиции дельфинов. Изначально будет дано описание N дельфинов.Всего следует проследить за M деревьями. Каждый дельфин изначально сидит на верхушке какого-то дерева. Каждый дельфин в течении одной секунды может с равной вероятностью перелететь на любое дерево с номером взаимно простым с номером того дерева, на котором сидит дельфин (т.е. таким, что наибольший общий делитель раівен 1), либо остаться на том де дереве. То есть, если деревьев 6, и дельфин сидит на дереве под номером 3, то события "дельфин через секунду окажется на дереве под номером 1 (или 2, 3, 4, 5)" – равновероятны.
Для проверки того, что Ваш алгоритм правильный, виведитеь сумму математических ожиданий количества дельфинов на деревьях (через T секунд). То есть, если m_1, m_2, ..., m_M – математичнеские ожидания количества дельфинов соответственно на первом, втором, ..., M-м дереве, то нужно вычислить
Входные данные
Первая строка содержит три целых числа, разделённых пробелами: N, M, T (1 ≤ M, N, T ≤ 1000) – количество дельфинов, количество деревьев и время, которое нужно промоделировать. Вторая строка содержит N целых чисел, разделённых пробелами, соответственно начальные расположения дельфинов (деревья нумеруются числами от 1 до M).
Выходные данные
В единственной строке вывести результат вычислений с двумя знаками после запятой.