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.