EIU Programming Practices and Exams

Duy is a professional gamer of League of Legends. Bcause he often forgets his game password, Duy wrote it down on a piece of paper.

One unlucky day, the pet dog Warwick accidentally bit the paper. After picking up all the pieces of paper, Duy wasn't sure what the order was for his password, but Duy was sure all the characters were there.

Currently Duy really needs to enter the game to practice for the upcoming world final, so he intends to ask a friend to help him list all the cases. Duy will try to log in until he succeeds and Duy promises to give an ultimate outfit to anyone who can help Duy.

Input

A string with N capital letters (1<=N<=9)

Output

The first line is M, the number of possible passwords.

The next M lines are instances of the password sorted lexicographically.

Note: Pseudocode for this problem in Text Book page 172 (Introduction to the Design & Analysis of Algorithms)

https://drive.google.com/file/d/16iW_BgVoOVp1rFhriVjwL4cNH3AyVEZ6/view?usp=drive_link

Example

Input:
ABC
Output:
6
ABC
ACB
BAC
BCA
CAB
CBA