Tehtäväsi on laskea, montako erilaista merkkijonoa leimasimen avulla voidaan muodostaa. Leimasin toimii samalla tavalla kuin kierroksen 2 tehtävässä B, ja jokainen merkkijonon kohta tulee leimata vähintään kerran.

Esimerkiksi kun merkkijonon pituus on 7, leimasimella aba voidaan tuottaa 12 erilaista merkkijonoa: aaaaaba, aaaabaa, aaabaaa, aaababa, aabaaaa, aabaaba, aababaa, abaaaaa, abaaaba, abaabaa, ababaaa, abababa.

Koska erilaisten merkkijonojen määrä saattaa olla suuri, sinun tulee ilmoittaa vastaus modulo 10^9+7.

Syöte

Ensimmäisellä rivillä on kaksi kokonaislukua n ja m: merkkijonon pituus ja leimasimen pituus.

Seuraavalla rivillä on merkkijono, joka kuvaa leimasimen. Voit olettaa, että leimasin muodostuu merkeistä a–z.

Tuloste

Tulosta yksi kokonaisluku: merkkijonojen määrä modulo 10^9+7.

Esimerkki 1

Syöte:

7 3
aba

Tuloste:

12

Esimerkki 2

Syöte:

20 7
aybabtu

Tuloste:

28651

Osatehtävä 1 (18 pistettä)

• 1 \le n \le 20
• 1 \le m \le 10

Osatehtävä 2 (19 pistettä)

• 1 \le n \le 100
• 1 \le m \le 50

Osatehtävä 3 (20 pistettä)

• 1 \le n \le 1000
• 1 \le m \le 50

Osatehtävä 4 (21 pistettä)

• 1 \le n \le 10^6
• 1 \le m \le 50

Osatehtävä 5 (22 pistettä)

• 1 \le n \le 10^9
• 1 \le m \le 50