Output-Restricted Double-Ended Queue Simulation

Problem Description

You are given an output-restricted double-ended queue. "Output-restricted" means: at one end you may both push and pop an element, but at the other end you may only push and cannot pop. In each step you may perform exactly one of the following three operations:

1. Push a character onto the left end.
2. Push a character onto the right end.
3. Pop the leftmost character.

You are given $n$ characters as the input of the queue. How many possible dequeue orders are there? Print all of them in lexicographic order.

Input Format

The first line contains an integer $n$, the length of the input.

The second line contains a string of length $n$.

Output Format

The first line contains an integer $k$, the number of possible dequeue orders.

The following $k$ lines output each possible dequeue order in lexicographic order.

Sample Input

3
123

Sample Output

6
123
132
213
231
312
321

Constraints

For all test data, $1 \le n \le 7$.