- Time limit: 1.00 s
- Memory limit: 512 MB
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
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$
- $1 \le n \le 100$
- $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
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$
- $1 \le n \le 100$
- $1 \le n \le 10^6$