Tính số cách có thể sắp xếp lại các ký tự của một chuỗi sao cho không có hai ký tự liền kề nào giống nhau.

Ví dụ, kết quả cho aabc là \(6\), vì các thứ tự có thể là abac, abca, acab, acba, baca và caba.

Input

• Một dòng duy nhất chứa một chuỗi \(n\) ký tự từ a - z.

Output

• Một số nguyên duy nhất: kết quả sau khi được modulo cho \(10^9 + 7\).

Constraints

• \(1\leq n \leq 5000\)

Example

Sample input

aabc

6