Tạo các chuỗi

Nguồn: CSES Problem Set

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho một chuỗi $s$ gồm $n$ ký tự chữ cái thường tiếng Anh.

Hãy tạo ra tất cả các chuỗi phân biệt có thể thu được bằng cách sắp xếp lại toàn bộ các ký tự của $s$.

Mỗi ký tự của chuỗi ban đầu phải được sử dụng đúng số lần nó xuất hiện trong $s$. Nếu một ký tự xuất hiện nhiều lần thì việc hoán đổi vị trí giữa các lần xuất hiện giống nhau không tạo thành một chuỗi mới.

Gọi $k$ là số chuỗi phân biệt có thể tạo được.

Các chuỗi kết quả phải được in theo thứ tự từ điển tăng dần.

Input

Dòng duy nhất chứa chuỗi $s$ gồm $n$ ký tự.

Mỗi ký tự của $s$ thuộc khoảng từ a đến z.

Output

Dòng đầu tiên in số nguyên $k$ — số chuỗi phân biệt có thể tạo được từ các ký tự của $s$.

Tiếp theo in $k$ dòng, mỗi dòng chứa một chuỗi kết quả.

Các chuỗi phải được in theo thứ tự từ điển tăng dần.

Subtask

• Subtask 1 — 10%: $1 \le n \le 6$.
• Subtask 2 — 20%: $1 \le n \le 9$.
• Subtask 3 — 30%: $1 \le n \le 14$; nếu $10 \le n \le 14$ thì tồn tại một ký tự xuất hiện ít nhất $n-4$ lần.
• Subtask 4 — 40%: $1 \le n \le 2000$; nếu $10 \le n \le 14$ thì tồn tại một ký tự xuất hiện ít nhất $n-4$ lần; nếu $15 \le n \le 2000$ thì tồn tại một ký tự xuất hiện ít nhất $n-1$ lần.

Ví dụ

Input

aabac

Output

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

Giải thích

Chuỗi aabac có $5$ ký tự, trong đó ký tự a xuất hiện $3$ lần, còn b và c mỗi ký tự xuất hiện một lần.

Nếu phân biệt cả ba ký tự a thì có $5!$ cách sắp xếp. Tuy nhiên ba ký tự a giống nhau nên mỗi chuỗi thực tế bị tính lặp $3!$ lần. Vì vậy số chuỗi phân biệt là

Output chứa đúng $20$ chuỗi phân biệt và được sắp xếp theo thứ tự từ điển tăng dần, bắt đầu từ aaabc và kết thúc bằng cbaaa.