Мавпа за клавіатурою
Ведучі телепередачі "Цікава математика" вирішили переконати глядачів у справедливости відомого вислову про те, що мавпа, яку посадили за клавіатуру і яка випадковим чином натискує на клавіші, згідно теорії ймовірності, рано чи пізно набере потрібне слово.
Мавпа, яку для зйомок надав міський зоопарк, вже навчена работі за клавіатурою — один раз в секунду вона з однаковою ймовірністю набирає одну з N перших букв латинського алфавіту. За щасливою випадковістю, у слові, підготовленому ведучими, також використовуються лише ці N букв.
Проте перед тем, як заставити мавпу потрудитись, ведучі хочуть знати, скільки часу у неї займе робота. Точніше, через скільки секунд у рядку, набраному мавпою, зустрінеться вказане слово?
Вхідні дані
Перший рядок містить число N — кількість символів, які вміє набирати мавпа (1 ≤ N ≤ 26). У другому рядку записано запропоноване ведучими слово. Слово може містити лише рядкові букви, які є одними з перших N символів латинського алфавіту. Довжина слова додатна і не перевищує 30000.
Вихідні дані
Виведіть очікуваний час, який мавпа затратить на роботу, округлений донизу до найближчого цілого числа.