eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дельфіни

Дельфіни

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Весна… Крілики радіють сонечку, небо стало добрим і м’яким, з’явились квіти, дельфіни прилетіли з теплих країв.

Справді! Дельфіни для кріликів – символ весни. Адже вони так чудово співають, літають, кружляють. Така поведінка дельфінів тішить майже всіх. Майже… Вченим кріликам з Інституту контролю за популяцією дельфінів у верхівках дерев Кріляндії радісна пора підкидає купу роботи. Їм потрібно контролювати цілі зграї дельфінів. Але вони сподіваються, що ми розробимо для них алгоритм прогнозування популяцій дельфінів у верхівках дерев.

Отже, потрібно написати програму, яка визначає імовірні позиції дельфінів. Спочатку буде задано опис N дельфінів. Усього потрібно слідкувати за M деревами. Кожен дельфін спочатку сидить на верхівці якогось дерева. Кожен дельфін за одну секунду з однаковою імовірністю може перелетіти на будь-яке дерево з номером взаємно простим з номером того дерева, на якому він сидів (взаємно прості числа мають найбільший спільний дільник, що дорівнює 1), або залишитися на місці. Таким чином, якщо дерев 6, і дельфін сидить на дереві з номером 3, то події "дельфін через секунду буде на дереві з номером1 (або2, 3, 4, 5)" – рівноможливі.

Для перевірки того, що Ваш алгоритм правильний, виведіть суму математичних сподівань кількості дельфінів на деревах (через T секунд). Тобто, якщо m_1, m_2, ..., m_M – математичні сподівання кількості дельфінів відповідно на першому, другому, ..., M-му дереві, то потрібно обчислити

Вхідні дані

Перший рядок містить три цілих числа, відокремлені пропусками: N, M, T (1M, N, T1000) – кількість дельфінів, кількість дерев і час відповідно, які потрібно змоделювати. Другий рядок містить N цілих чисел, відокремлених пропусками, що задають початкове розташування дельфінів (дерева пронумеровані числами від 1 до M).

Вихідні дані

У єдиному рядку вивести результат обчислень з двома знаками після коми.

Приклад

Вхідні дані #1
1 1 1
1
Вихідні дані #1
1.00
Джерело ACM-ICPC Ukraine 2012, 1st Stage Ukraine, April 21, 2012