- Time limit: 1.00 s
- Memory limit: 512 MB
For example, the answer for
aabc
is $6$, because the possible orders are abac
, abca
, acab
, acba
, baca
, and caba
.Input
The only input line has a string that consists of $n$ characters between
a
–z
.Output
Print an integer: the answer modulo $10^9+7$.
Constraints
- $1 \le n \le 5000$
Input:
aabc
Output:
6