Дельфіни
Дельфіни
Весна… Крілики радіють сонечку, небо стало добрим і м’яким, з’явились квіти, дельфіни прилетіли з теплих країв.
Справді! Дельфіни для кріликів – символ весни. Адже вони так чудово співають, літають, кружляють. Така поведінка дельфінів тішить майже всіх. Майже… Вченим кріликам з Інституту контролю за популяцією дельфінів у верхівках дерев Кріляндії радісна пора підкидає купу роботи. Їм потрібно контролювати цілі зграї дельфінів. Але вони сподіваються, що ми розробимо для них алгоритм прогнозування популяцій дельфінів у верхівках дерев.
Отже, потрібно написати програму, яка визначає імовірні позиції дельфінів. Спочатку буде задано опис 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).
Вихідні дані
У єдиному рядку вивести результат обчислень з двома знаками після коми.
Приклад
1 1 1 1
1.00