Sinulle on annettu merkkijono. Saat poistaa siitä merkkejä haluamallasi tavalla, kunhan jäljelle jäävien merkkien järjestys säilyy samana.

Montako erilaista merkkijonoa pystyt muodostamaan tällä tavalla?

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on n merkkiä. Jokainen merkki on aakkonen välillä a–z.

Tuloste

Ohjelmasi tulee tulostaa yksi kokonaisluku: erilaisten merkkijonojen määrä modulo 10^9+7.

Rajat

• 1 \le n \le 10^5

Esimerkki

Syöte:

aybabtu

Tuloste:

103