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