Задача Ітана Ганта#343
Ітан Гант, герой серії "Місія нездійсненна", відомий своїми навичками диверсанта. Проте був випадок, коли ЦРУ залучило його для оцінки надійності своїх дверних кодів. Як показано у популярних фільмах, кодові замки ЦРУ зазвичай відкриваються за допомогою магнітної картки. Припустимо, ця картка містить послідовність бітів довжини . Коли ці біти зчитуються, якщо вони співпадають із кодом дверей, двері відчиняються. На запитання, як би він відкрив такий замок, Гант запропонував наступний підхід.
Уявімо довгу магнітну стрічку, на яку ми записуємо довільну послідовність довжини (N \geq M), складену з та , причому кожен біт має однакову ймовірність бути або . Далі ми проводимо цю стрічку через замок. Якщо код замка зустрічається в цій послідовності, замок відкривається. (Примітка: Це голлівудський фільм — тому невідповідність між фізичним кодуванням суцільної стрічки й магнітною карткою нас не цікавить.)
Керівництво ЦРУ вирішило оцінити всі коди замків на стійкість до методу Ганта.
У першому рядку задано число (1 \leq N \leq 60) — довжина бітової послідовності, записаної на стрічці. У другому рядку задано код замка — непорожній рядок із символів "0" і "1", довжина якого не перевищує .
Виведіть ймовірність того, що код замка з'явиться у випадково згенерованій послідовності бітів довжини . Ймовірність слід подати у вигляді нескоротного дробу, у чисельнику і знаменнику якого стоять цілі числа, розділені символом "/".
Приклад 1