Задача Итана Ханта
Герой сериала "Миссия невыполнима" Итан Хант известен больше как диверсант. Однако однажды ЦРУ привлекло его в качестве эксперта по оценке надёжности кодов дверей в ЦРУ. Как известно (в основном, по популярным фильмам), кодовые замки в ЦРУ открываются с помощью магнитной карточки. Будем считать, что на этой карточке записана последовательность битов длины M. Последовательность битов считывается, и если записанные биты совпадают с кодом двери, дверь открывается. У Ханта спросили, как бы он вскрывал такой замок, и тот предложил следующую идею.
Возьмём длинную магнитную ленту, запишем на неё произвольную последовательность длины N (N ≥ M) из 0 и 1, такую, что вероятность встретить в ней на каждой позиции 0 или 1 одинаковы. Затем проведём этой лентой по замку. Если в этой последовательности где-то встретился код замка, замок откроется (напомним, что дело происходит в голливудском фильме, и то, что физическая кодировка сплошной ленты и магнитной карты никак не совпадают, не столь важно).
В дирекции ЦРУ подумали и решили проверить все коды замков на хантоустойчивость.
Входные данные
В первой строке число N - длина последовательности битов, записанных на ленте ( 1 ≤ N ≤ 60). Во второй строке – код замка, т.е. непустая строка, состоящая из символов "0" и "1", длина которой не превышает N.
Выходные данные
Вероятность наличия кода замка в произвольно взятой последовательности битов длины N. Вероятность выдается в виде несократимой дроби, числитель и знаменатель которой разделены символом "/".