Одного разу Олег купив собі новий ноутбук. Олег - великий любитель трохи застарілої операційної системы \textit{\textbf{Dindows PX}}. Але, як відомо, сучасні ноутбуки поставляються з наперед встановленою \textit{\textbf{ОС Dindows версии 18}}. Так що Олег, недовго думаючи, видалив напред встановлену \textit{\textbf{Dindows 18}} і встановив таку любиму ним версію \textit{\textbf{PX}}. Зрозуміло, усе було далеко не так просто, адже виробники заліза часто закидабть написання нормальних драйверів для дещо застарілих операційних систем. Так що довгими днями та безсонними ночами боровся Олег з зависаннями та Зеленими Екранами Життя. І ось, нарешті, у нього це вийшло! Не було муж радощам Олега... По меншій мірі, до тих пір, доки не вияснилось, що половина заліза працює не зовсім коректно. Але хіба могло це його зупинити? І ось, одного разу перед Олегом постала саступна задача: надрукувати деякий текст \textbf{S} довжини \textbf{n}. Здавалось би, що може бути простіше? Якби би лише не один маленький баг з клавіатурою - після завантаження ноутбука деякі символи на клавіатурі не працюють. Судячи за спостереженнями Олега, після кожного перезавантаження працює рівно \textbf{t }латинських символів, які кожного разу обираються випадково з рівною ймовірністю. Спочатку у Олега є порожній файл. Він може дописувати нові символи лише у кінець файлу, і вже написаний текст зберігається перед кожним перезавантаженням, так що він може продовжити його редагування після перезавантаження зі збереженого місця. Олег хоче порахувати маточікування кількості перезавантажень, які йому прийдеться здійснити, щоб повністю надрукувати текст \textbf{S}. Зрозуміло, він і сам би легко написав потрібну програму, але з його-то клавіатурою це досить проблематично, тому він попросив вас допомогти йому. \InputFile У першому рядку вхідного файлу знаходиться два числа \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10^6}) та \textbf{t} (\textbf{1} ≤ \textbf{t} ≤ \textbf{26}). У другому рядку знаходиться рядок \textbf{S} довжини \textbf{n}, який складається з рядкових латинських букв. \OutputFile Виведіть шукане маточікування з абсолютною чи відносною похибкою не більше, чем \textbf{10 ^\{- 6\}}.