ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1677. Обезьяна за клавиатурой

Ограничение времени: 5.0 секунды
Ограничение памяти: 64 МБ
Ведущие телепередачи «Занимательная математика» решили убедить зрителей в справедливости известного утверждения о том, что обезьяна, посаженная за клавиатуру и случайным образом нажимающая на клавиши, согласно теории вероятности, рано или поздно наберёт нужное слово.
Обезьяна, которую для съёмок предоставил городской зоопарк, уже обучена работе за клавиатурой — один раз в секунду она с равной вероятностью набирает одну из N первых букв латинского алфавита. По счастливой случайности, в слове, подготовленном ведущими, тоже используются только эти N букв.
Однако перед тем, как заставить обезьяну трудиться, ведущие хотят знать, сколько времени у неё займёт работа. Точнее, через сколько секунд в строке, набранной обезьяной, встретится указанное слово?

Исходные данные

Первая строка содержит число N — количество символов, которые умеет набирать обезьяна (1 ≤ N ≤ 26). Во второй строке записано предложенное ведущими слово. Слово может содержать только строчные буквы, являющиеся одними из первых N символов латинского алфавита. Длина слова положительна и не превосходит 30000.

Результат

Выведите ожидаемое время, которое обезьяна потратит на работу, округлённое вниз до ближайшего целого числа.

Примеры

исходные данныерезультат
2
aa
6
2
ba
4
Автор задачи: Игорь Чевдарь
Источник задачи: Ural SU Contest. Petrozavodsk Summer Session, August 2008