Cho một xâu, nhiệm vụ của bạn là sinh ra tất cả các xâu khác nhau có thể được tạo từ các ký tự của nó.

Dữ liệu vào

Dòng duy nhất chứa một xâu có độ dài ~n~. Mỗi ký tự nằm trong khoảng a–z.

Kết quả

Đầu tiên in ra một số nguyên ~k~: số lượng xâu. Sau đó in ra ~k~ dòng: các xâu theo thứ tự bảng chữ cái.

Giới hạn

• ~1 \le n \le 8~

Ví dụ

Dữ liệu vào:

aabac

Kết quả:

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