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

Обезьяна, которую для съёмок предоставил городской зоопарк, уже обучена работе за клавиатурой — один раз в секунду она с равной вероятностью набирает одну из N первых букв латинского алфавита. По счастливой случайности, в слове, подготовленном ведущими, тоже используются только эти N букв.

Однако перед тем, как заставить обезьяну трудиться, ведущие хотят знать, сколько времени у неё займёт работа. Точнее, через сколько секунд в строке, набранной обезьяной, встретится указанное слово?

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

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