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.