CSES - 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.