CNU10 | Substring

Cerință

Cate cuvinte de lungime $N$ exista care sa contina ca substring cuvantul $X$?

Date de intrare

Pe prima linie este $N$. Pe a doua linie este cuvantul $X$.

Date de ieșire

Numarul de cuvinte cerut modulo $10^9+7$.

Restricții și precizări

• $1 \leq N \leq 1000$
• $1 \leq |X| \leq 100$, $|X|$ este lungimea cuvantului $X$
• Cuvintele trebuie sa fie formate doar din litere mari $A...Z$

Exemplul 1

stdin

6
ABCDB

stdout

52

Explicație

Toate cuvintele de forma $xABCDB$ si $ABCDBx$ sunt bune.

Exemplul 2

stdin

122
AABA

stdout

956357460