​ 给你一个输出受限的双端队列，限制输出的双端队列即可以从一端插入元素，弹出元素，但是另一端只可以插入不可以删除元素。即每次你可以执行以下三种操作的其中一种：

1. 在左边压入一个字符

2. 在右边压入一个字符

3. 弹出最左边的字符

​ 现在给你 $n$ 个字符作为队列的输入，请问最多有多少可能的出队次序，并按字典序打印这些出队次序。

输入格式

​ 第一行一个数 $n$，表示输入的长度

​ 第二行一个长度为 $n$ 的字符串

输出格式

​ 第一行一个整数 $k$，表示可能的出队方案数

​ 下面 $k$ 行，按字典序输出每种出队方案

样例输入

3
123

样例输出

6
123
132
213
231
312
321

数据规模

​ 对于全部数据保证 $1 \leq n \leq 7$。