Given a string, your task is to generate all different strings that can be created using its characters.

Input

• The only input line has a string of length \(n\). Each character is between a-z.

Output

• First print an integer \(k\): the number of strings. Then print \(k\) lines: the strings in alphabetical order.

Constraints

• \(1 \leq n \leq 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