#include
#include
#include
using namespace std;
template
void quicksort(vector& a, int left, int right, vector& next)
{
int L = left, R = right;
eT T = a[L];
while (L < R) {
while (a[R] >= T && L < R) --R;
a[L] = a[R];
while (a[L] < T && L < R) ++L;
a[R] = a[L];
}
int M1 = L;
R = right;
while (L < R) {
while (a[R] > T && L < R) --R;
a[L] = a[R];
while (a[L] <= T && L < R) ++L;
a[R] = a[L];
}
a[L] = T;
int M2 = L;
for (int i = M1; i <= M2; ++i)
next[i] = M2 + 1;
if (left < M1 - 1)
quicksort(a, left, M1 - 1, next);
else if (left == M1 - 1)
next[left] = M1;
if (M2 + 1 < right)
quicksort(a, M2 + 1, right, next);
else if (M2 + 1 == right)
next[right] = right + 1;
}
int arrange(vector& elems, vector& next, vector& used, vector& rec)
{
int i = 0, n = elems.size();
while (i < n && used[i]) ++i;
if (i >= n) {
for (i = 0; i < n; ++i)
cout << rec[i];
cout << endl;
return 1;
}
int cnt = 0;
while (i < n) {
rec.push_back(elems[i]);
used[i] = 1;
cnt += arrange(elems, next, used, rec);
rec.erase(rec.end()-1);
used[i] = 0;
i = next[i];
while (i < n && used[i]) ++i;
}
return cnt;
}
int main(void)
{
int n;
while (cin >> n) {
while (getchar() != '
');
vector elems;
for (int i = 0; i < n; ++i) {
elems.push_back(getchar());
}
while (getchar() != '
');
vector next(n, -1);
quicksort(elems, 0, n - 1, next);
// display
for (int i = 0; i < n; ++i)
cout << elems[i] << " ";
cout << endl;
for (int i = 0; i < n; ++i)
cout << next[i] << " ";
cout << endl;
// arrange
vector used(n, 0);
cout << endl;
cout << arrange(elems, next, used, vector()) << endl;
}
return 0;
}