Tehtäväsi on laskea, montako n-merkin pituista aakkoston A–Z merkkijonoa on olemassa, joissa esiintyy osajonona annettu merkkijono ainakin kerran.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: merkkijonon pituus.

Syötteen toisella rivillä on merkkijono, jossa on m merkkiä väliltä A–Z.

Tuloste

Tulosta haluttujen merkkijonojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 1000
• 1 \le m \le 100

Esimerkki

Syöte:

6
MAIJA

Tuloste:

52

Selitys: Merkkijono voi olla muotoa MAIJAx tai xMAIJA, missä x on mikä tahansa merkki.