Ositus (Partitioning)

• Time limit: 1.00 s
• Memory limit: 512 MB

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$
  

---

Your task is to compute in how many ways a given string may be partitioned, such that no part contains the same character twice.

For the string abac, for example, the possible partitions are:

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

Because the answer to the task may be a large number, print the answer modulo $10^9+7$, i.e. the remainder when dividing the answer
by the number $10^9+7$.

Input

The only line of input contains a string which has $n$ characters among a–z.

Output

Print one integer: the answer to the task modulo $10^9+7$.

Example

Input:
aybabtu

Output:
44

Subtask 1 (40 points)

• $1 \le n \le 10$
  

Subtask 2 (25 points)

• $1 \le n \le 100$
  

Subtask 3 (35 points)

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