29188번 - Каждая пони умеет писать 다국어

Две недели назад принцесса Селестия попросила всех пони научиться писать к званому вечеру во дворце Селестии. Эпплджек все эти две недели так была занята на своей ферме, что совсем забыла об этом. Осталась всего пара часов, а она понятия не имеет как написать хоть какое-нибудь слово. Хорошо, что Твайлайт Спаркл оказалась неподалеку.

<<Вот кто сможет выручить меня>> --- подумала Эпплджек и обратилась к Твайлайт за помощью. Началось обучение.

В течение часа Эпплджек пыталась вникнуть в это занимательное мастерство, но к сожалению смогла овладеть лишь написанием одного слова.

<<Как же мне быть, сахарок? Принцесса Селестия прознает о том, что я умею писать всего одно слово>> --- c расстройством сказала Эпплджек.

<<На самом деле ты умеешь писать не одно слово. Все слова в нашем языке обладают одним интересным свойством: если $s$ ---слово, а $p$ ---префикс $s$, то $sp$ --- также является словом. Но обычно пони не пишут слишком длинные или короткие слова, слова длины $n$ ---считаются наиболее вежливыми и пони стараются писать только их>> --- ответила Твайлайт.

<<И много слов длины $n$ я смогу написать?>> --- спросила Эпплджек.

<<Ну это надо посчитать. Ты полностью поняла алгоритм построения слов?>> --- спросила Твайлайт и задумалась.

<<Да, конечно, это же совсем просто. Кстати, что такое префикс?>> --- радостно ответила Эпплджек.

Пока Твайлайт объясняет Эпплджек, что такое префикс, посчитайте количество различных слов, которые Эпплджек сможет написать. Без вашей помощи они не успеют.

Первая строка входного файла содержит целое число $n$ ($1 \le n \le 5{\,}000$) --- длины слов, которые необходимо получить. Вторая строка содержит строку длины $k$ ($1 \le k \le n$) состоящую из строчных латинских букв --- единственная строка, которую знает Эпплджек.

В выходной файл выведите единственно число --- количество различных строк, которые сможет получить Эпплджек из исходной. Разумеется после того, как узнает, что такое префикс. Количество нужно вывести по модулю $10^9 + 7$. (Что такое модуль Эпплджек конечно же знает)