Cho một xâu, nhiệm vụ của bạn là đưa ra kết quả của tất cả các xâu có thể được tạo ra sử dụng những kí tự của xâu đã cho.

Input

• Một dòng chứa một xâu có độ dài \(n\). Các kí tự nằm trong pham vi từ a-z.

Output

• Dòng đầu tiên in ra số \(k\) (với \(k\) là số xâu có thể được tạo ra từ xâu ban đầu). Sau đó, in ra \(k\) dòng là các xâu được sắp xếp theo thứ tự từ điển.

Constraints

• \(1 \le n \le 8\)

Example

Sample input

aabac

Sample output

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