Salasana

• Time limit: 1.00 s
• Memory limit: 512 MB

Uolevi on unohtanut salasanansa, ja muistaa siitä vain kaksi asiaa. Ensinnäkin salasanassa on $n$ merkkiä väliltä A..Z. Lisäksi salasanassa esiintyy jossakin kohtaa Uolevin kannattaman jääkiekkojoukkueen nimi.

Montako mahdollista salasanaa täyttää nämä ehdot?

Syöte

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

Syötteen toisella rivilllä on merkkijono, jossa on $k$ merkkiä väliltä A..Z: Uolevin kannattaman jääkiekkojoukkueen nimi.

Tuloste

Ohjelmasi tulee tulostaa mahdollisten salasanojen määrä modulo $10^9+7$.

Rajat

• $1 \le n \le 1000$
  
• $1 \le k \le \min(n,20)$
  

Esimerkki

Syöte:
15
TAPPARA

Tuloste:
443567953

Selitys: Mahdollisia salasanoja ovat esimerkiksi ABCDTAPPARAABCD sekä TAPPARAXTAPPARA.