说明

设 $R=\{ r_1, r_2, ……, r_n\}$ 是要进行排列的 $n$ 个元素，其中可能有重复元素。

试设计一个算法，按照字典序列出所有不同排列。

输入格式

输入数据的第1行是元素个数 $n(1≤n≤9)$，接下来的1行是待排列的 $n$ 个元素

输出格式

按照字典序将计算出的 $n$ 个元素的所有不同排列输出，每种排列占1行，最后1行中的数是排列总数

样例

4
aacc

aacc
acac
acca
caac
caca
ccaa
6