Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 www.vietnamson.com

Đề thi chọn học sinh giỏi lớp 12 cấp Thành phố – TP. Đà Nẵng — Năm học 2021 - 2022 — Bài 4

Một xâu được gọi là đối xứng khi viết từ phải qua trái hay từ trái qua phải thì xâu đó không thay đổi. Nguyên là một người rất yêu thích xâu đối xứng và các bài toán liên quan về nó. Vào một ngày, anh ấy gặp bài toán như sau: Cho trước một xâu ~S~ gồm ký tự in hoa A-Z. Hãy đếm số lượng xâu đối xứng có thể thu được bằng cách sắp xếp lại các ký tự trong xâu ~S~.

Tuy rất giỏi về các bài toán về xâu đối xứng, nhưng hiện tại anh ấy vẫn chưa thể nghĩ ra ý tưởng cho bài toán này. Vì thế anh ấy rất muốn bạn giải quyết bài toán này.

Input

Dữ liệu vào từ bàn phím (stdin): một dòng duy nhất chứa xâu ~S~.

Output

In ra màn hình (stdout) một số nguyên là số lượng xâu đối xứng có thể thu được (lấy phần dư của kết quả khi chia cho ~M = 10^9 + 7~).

Scoring

• ~50\%~ test: Độ dài của xâu ~S~ không quá ~10~ ký tự.
• ~50\%~ test: Độ dài của xâu ~S~ không quá ~10^6~ ký tự.

Sample Input 1

ABBAA

Sample Output 1

2

Notes

Có ~2~ xâu đối xứng thu được là: ABABA và BAAAB.

Ghi chú (bổ sung trên CLUE OJ): đề gốc đọc/ghi file CNTPALIN.INP / CNTPALIN.OUT; trên CLUE OJ em đọc từ bàn phím và in ra màn hình.