영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
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 ≤ n ≤ 5000
예제
예제 1
aabc
6