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

Задача Ітана Ханта

Задача Ітана Ханта

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

Герой серіалу "Місія невиконувана" Ітан Хант відомий більше як диверсант. Однак одного разу ЦРУ використало його в якості експерта по оцінці надійності кодів дверей в ЦРУ. Як відомо (в основному, з популярних фільмів), кодові замки в ЦРУ відкриваються при допомозі магнітної картки. Будемо вважати, що на цій картці записано послідовність бітів довжини M. Послідовність бітів зчитується, і якщо записані біти співпадають з кодом дверей, двері відкриваються. У Ханта запитали, як би він вскривав такий замок, і той запропонував наступну ідею.

Візьмемо довгу магнітну стрічку, запишемо на неї довільну послідовність довжини N (NM) з 0 і 1, таку, що ймовірність зустріти у ній на кожній позиції 0 або 1 однакові. Потім проведемо цією стрічкою по замку. Якщо у цій послідовності десь зустрівся код замка, замок відкриється (нагадаємо, що події відбуваються у голівудьскому фільмі, і те, що фізичне кодування суцільної стрічки і магнітної картки ніяк не співпадають, не такь важливо).

В дирекції ЦРУ подумали і вирішили перевірити всі коди замків на хантостійкість.

Вхідні дані

У першому рядку задано число N - довжину послідовності бітів, записаних на стрічці ( 1N60). У другому рядку – код замка, тобто непустий рядок, що містить символи "0" та "1", довжина якого не перевищує N.

Вихідні дані

Ймовірність наявності коду замка у довільно взятій послідовності бітів довжиниы N. Ймовірність виводиться у вигляді нескоротного дробу, чисельник і знаменник якого відокремлено символом "/".

Приклад

Вхідні дані #1
3
00
Вихідні дані #1
3/8