Thời gian luộc bánh Chưng thường khá lâu, có thể đến tiếng. Vì thời gian luộc bánh Chưng lâu như vậy nên trong thời gian này các bạn thường tìm các trò chơi để giết thời gian. Hạnh là một học sinh học rất giỏi Văn nên Hạnh lại tranh thủ sưu tầm câu đối cho ngày Tết (thay vì chơi các trò chơi khác). Và Hạnh đã tìm được một câu đối rất hay là một xâu ký tự . Lúc này có rất nhiều bạn đến xin “copy” câu đối của Hạnh. Tuy nhiên, mỗi bạn sau khi “copy”, vì không muốn câu đối của mình giống hoàn toàn của bạn Hạnh và của những bạn khác đã “copy” trước đó nên đã chọn một đoạn các ký tự liên tiếp và thay bằng chính đoạn ký tự đó nhưng theo thứ tự ngược lại. Nam là một học sinh giỏi Toán nên Nam lại đặt ra câu hỏi: Từ câu đối của Hạnh, với cách thức “copy” như trên (chỉ “copy” từ câu đối của Hạnh, tránh sự “tam sao thất bản”), có thể tạo ra bao nhiêu câu đối khác nhau (bao gồm cả câu đối của Hạnh)?
Là một học sinh giỏi Tin, em hãy giúp Nam trả lời câu hỏi trên nhé.
Dữ liệu vào:
Một dòng duy nhất chứa câu đối của bạn Hạnh là một xâu ký tự chỉ gồm các chữ cái la-tinh thường (‘a’, …., ‘z’).
Dữ liệu ra:
Một số nguyên dương duy nhất là số câu đối khác nhau có thể có.
Ví dụ:
Dữ liệu vào:
abab
Dữ liệu ra:
5
Giải thích:
có tất cả câu đối khác nhau là “abab”, “baab”, “aabb”, “baba”, “abba” (đoạn chữ đậm chính là đoạn được đảo ngược).
Giới hạn:
Trong tất cả các test, độ dài xâu không quá . Trong đó:
Subtask số test ứng với số điểm có độ dài xâu không quá .
Subtask số test khác ứng với số điểm có độ dài xâu không quá .
Subtask số test khác ứng với số điểm có chỉ chứa ký tự ‘a’, ‘b’.
Subtask số test còn lại ứng với số điểm không có ràng buộc gì thêm.
