Haluat muodostaa merkkijonon, jonka pituus on n merkkiä ja joka muodostuu merkeistä A–Z. Lisäksi on kielletty sana, jota ei saa esiintyä merkkijonon osana.

Monellako tavalla voit muodostaa merkkijonon?

Syöte

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

Seuraavalla rivillä on kielletty sana, joka muodostuu merkeistä A–Z ja jonka pituus on enintään n.

Tuloste

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

Rajat

• 1 \le n \le 500

Esimerkki

Syöte:

4
ABC

Tuloste:

456924