Задається рядок довжиною ~n~ символів.

Ваше завдання полягає в тому, щоб створити всі рядки, які можна отримати із символів заданого рядка.

Обмеження

~1 \le n \le 8~

Input

Єдиний вхідний рядок містить рядок довжини ~n~. Кожен символ знаходиться між a–z.

Output

Спочатку виведіть ціле число ~k~: кількість рядків. Потім виведіть ~k~ рядків: знайдені рядки в алфавітному порядку.

Sample Input 1

aabac

Sample Output 1

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