F - Ultimul Cox

Enunt

Ai o tastatură cu $27$ de taste și anume: toate literele mici din alfabetul englez și tasta Backspace.

Ai o bară de căutare care ințial e vidă, odată cu apăsarea unei taste care nu este Backspace litera corespunzătoare tastei este scrisă la sfârșitul cuvântului din bara de căutare.
Dacă tasta apăsată este Backspace se va șterge ultima literă din bara de căutare, dacă există una, altfel nu se va întampla nimic.

Se dă $N$ și un sir de caractere, în cate feluri poți ajunge la șirul dat după apăsarea a exact $N$ taste?

Input

Pe prima linie este $N$. Pe a doua linie se află șirul de caractere la care trebuie să ajungi.

Output

Numarul de moduri să ajungi la șirul dat modulo $10^9+7$, care este un număr prim.

Restrictii

• $1 \le \text{lungimea sirului dat} \le N \le 5000$.

Exemplu

stdin

3
a

stdout

53

Explicatie

Dacă notăm cu B un backspace, modurile de a ajunge la șirul a sunt:
aBa, bBa, ... , zBa - $26$ de moduri
BBa - $1$ mod
aaB, abB, ..., azB - $26$ moduri

În total, sunt $53$ de moduri.