Dada una cadena, tu tarea es generar todas las cadenas diferentes que se pueden crear usando sus caracteres.

Entrada

La única línea de entrada tiene una cadena de longitud ~n~. Cada carácter está comprendido entre a-z.

Salida

Primero imprime un número entero ~k~: el número de cadenas. Luego imprime ~k~ líneas: las cadenas en orden alfabético.

Restricciones

• ~1 \leq n \leq 8~.

Ejemplo de Entrada

aabac

Ejemplo de Salida

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