Xáo trộn chữ cái

Cho một từ \(W\) gồm các chữ cái Latinh. Bằng cách xáo trộn (hoán đổi vị trí) các chữ cái của \(W\) ta thu được các từ mới có cùng độ dài. Hãy liệt kê tất cả các từ khác nhau có thể tạo ra theo cách đó (bao gồm cả chính từ ban đầu).

Chẳng hạn từ pqp chỉ tạo được ba từ khác nhau là ppq, pqp và qpp, dù có ba chữ cái.

Input

Một dòng chứa từ \(W\) gồm các chữ cái Latinh (chữ hoa và chữ thường là hai ký tự khác nhau), độ dài từ \(1\) đến \(9\).

Output

• Dòng đầu tiên: số lượng từ khác nhau tạo được.
• Mỗi dòng tiếp theo: một từ. Các từ in theo thứ tự từ điển tăng dần (theo mã ASCII của ký tự).

Constraints

• \(1 \le |W| \le 9\)

Sample Input

pqp

Sample Output

3
ppq
pqp
qpp