Cho một xâu \(s\) chỉ gồm các ký tự latin in thường từ a đến z. Bạn hãy in ra tất cả các xâu khác nhau có thể tạo được bằng cách hoán đổi vị trí các ký tự của \(s\).

Input

• Một dòng duy nhất xâu \(s\) độ dài \(n\) với \(1\leq n\leq 8\).

Output

• Dòng đầu in ra số nguyên dương \(k\) thể hiện số lượng xâu khác nhau tạo được.
• \(k\) dòng tiếp theo in ra các xâu đó theo thứ tự từ điển tăng dần.

Ví dụ

Sample input 01

aabac

Sample output 01

20
aaabc
aaacb
aabac
aabca
aacab
aacba
abaac
abaca
abcaa
acaab
acaba
acbaa
baaac
baaca
bacaa
bcaaa
caaab
caaba
cabaa
cbaaa