CSES - Counting Reorders | Đếm số cách sắp xếp

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
nhphucqt
Dạng bài
Điểm: 1700 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

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

Sample output

6

Bình luận