CSES - Merkkijonot
  • Time limit: 1.00 s
  • Memory limit: 128 MB

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

Syöte

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

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

Tuloste

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

Rajat

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

Esimerkki

Syöte:

6
MAIJA

Tuloste:

52

Selitys: Merkkijono voi olla muotoa MAIJAxx tai xxMAIJA, missä xx on mikä tahansa merkki.