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

• Đọc từ file văn bản CNTPALIN.INP có một dòng duy nhất chứa xâu \(s\).

Output

• Ghi ra file văn bản CNTPALIN.OUT 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ự.

Example

ABBAA

2