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