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

Calculate the number of ways you can reorder the characters of a string so that no two adjacent characters are the same.

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

# Example

Input:

aabc

Output:

6