Задачі
Задача Ітана Ханта
Задача Ітана Ханта
Герой серіалу "Місія невиконувана" Ітан Хант відомий більше як диверсант. Однак одного разу ЦРУ використало його в якості експерта по оцінці надійності кодів дверей в ЦРУ. Як відомо (в основному, з популярних фільмів), кодові замки в ЦРУ відкриваються при допомозі магнітної картки. Будемо вважати, що на цій картці записано послідовність бітів довжини \textbf{M}. Послідовність бітів зчитується, і якщо записані біти співпадають з кодом дверей, двері відкриваються. У Ханта запитали, як би він вскривав такий замок, і той запропонував наступну ідею.
Візьмемо довгу магнітну стрічку, запишемо на неї довільну послідовність довжини \textbf{N}\textit{ (}\textbf{N}\textit{ }≥\textit{ }\textbf{M}\textit{) }з \textbf{0} і \textbf{1}, таку, що ймовірність зустріти у ній на кожній позиції \textbf{0} або \textbf{1} однакові. Потім проведемо цією стрічкою по замку. Якщо у цій послідовності десь зустрівся код замка, замок відкриється (нагадаємо, що події відбуваються у голівудьскому фільмі, і те, що фізичне кодування суцільної стрічки і магнітної картки ніяк не співпадають, не такь важливо).
В дирекції ЦРУ подумали і вирішили перевірити всі коди замків на хантостійкість.
\InputFile
У першому рядку задано число \textbf{N} - довжину послідовності бітів, записаних на стрічці ( \textbf{1} ≤ \textbf{N}\textit{ }≤ \textbf{60}). У другому рядку -- код замка, тобто непустий рядок, що містить символи "\textbf{0}" та "\textbf{1}", довжина якого не перевищує \textbf{N}.
\OutputFile
Ймовірність наявності коду замка у довільно взятій послідовності бітів довжиниы \textbf{N}. Ймовірність виводиться у вигляді нескоротного дробу, чисельник і знаменник якого відокремлено символом "\textbf{/}".
Вхідні дані #1
3 00
Вихідні дані #1
3/8