Tehtäväsi on laskea, monellako tavalla merkkijono voidaan jakaa osiin niin, että missään osassa ei esiinny kahta samaa merkkiä.

Esimerkiksi kun merkkijono on abac, mahdolliset jaot ovat:

• a+b+a+c
• a+b+ac
• a+ba+c
• a+bac
• ab+a+c
• ab+ac

Koska tehtävän vastaus voi olla suuri luku, tulosta vastaus modulo $10^9+7$ eli vastauksen jakojäännös luvulla $10^9+7$.

Syöte

Syötteen ainoalla rivillä on merkkijono, jossa on $n$ merkkiä ja joka muodostuu merkeistä a–z.

Tuloste

Tulosta yksi kokonaisluku: tehtävän vastaus modulo $10^9+7$.

Esimerkki

Syöte:

aybabtu

Tuloste:

44

Osatehtävä 1 (40 pistettä)

• $1 \le n \le 10$

Osatehtävä 2 (25 pistettä)

• $1 \le n \le 100$

Osatehtävä 3 (35 pistettä)

• $1 \le n \le 10^6$