Cho một xâu ~S~ chỉ gồm các chữ cái in hoa, ~1 \le~ độ dài ~\le 9~. Yêu cầu:

1. Có bao nhiêu cách hoán vị các chữ cái của xâu ~S~
2. Liệt kê các hoán vị đó theo thứ tự từ điển

Input

Gồm ~1~ dòng duy nhất chứa xâu ~S~

Output

• Dòng ~1~: Ghi số lượng hoán vị tìm được ~(K)~
• ~K~ dòng tiếp theo, mỗi dòng ghi một xâu hoán vị của xâu ~S~ theo đúng thứ tự từ điển

Sample Input

ABAB

Sample Output

6
AABB
ABAB
ABBA
BAAB
BABA
BBAA