iostream nổi tiếng là một người hiền lành, vì thế iostream luôn giao những công việc đơn giản cho dao-puppy. Hôm nay cũng vậy, iostream đưa cho dao-puppy môt chương trình mã hóa xâu và một xâu ~S~ có độ dài không vượt quá ~10^5~ kí tự chỉ gồm các chữ cái Latin thường. Chương trình mã hóa xâu sẽ hoạt động như sau:
Người dùng cần nhập vào chương trình một xâu có ít nhất ~2~ kí tự. Sau đó chương trình sẽ chọn ngẫu nhiên ~2~ số ~i~ và ~j~ khác nhau, đổi chỗ ~2~ kí tự ở ~2~ vị trí này rồi trả cho người dùng xâu sau khi đổi chỗ (hai chỉ số ~i, j~ không vượt quá độ dài của xâu).
Ví dụ xâu nhập vào là ~aba~, chương trình chọn được ~2~ số ~i~ và ~j~ là ~1~ và ~2~ thì chương trình sẽ trả về xâu ~baa~.
Dễ thấy rằng với cùng một xâu có thể cho ra nhiều kết quả mã hóa khác nhau. iostream muốn nhờ dao-puppy giúp mình ghi lại tất cả các xâu khác nhau có thể nhận được khi cho máy mã hóa xâu ~S~.
Bằng cách đưa xâu ~S~ vào chương trình mã hóa nhiều lần, dao-puppy đã ghi ra được rất nhiều xâu khác nhau nhưng không biết đã đủ hay chưa, bạn hãy giúp dao-puppy tính xem có tất cả bao nhiêu xâu khác nhau có thể nhận được bằng việc mã hóa xâu ~S~.
Input
- Một dòng duy nhất chứa xâu ~S~ ~(2 \leq |S| \leq 10^5)~
Output
- In ra số xâu khác nhau có thể nhận được
Sample Input
abca
Sample Output
6
Note
Các xâu khác nhau nhận được là ~abca, baca, cbaa, acba, aacb, abac~.
Bình luận