#include <bits/stdc++.h>
#define DIM 20
using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int a[DIM][DIM],f[DIM],x[DIM],v[DIM];
int n,nr_sol;
int verif (int x, int y){
    /// vreau sa pun dama in x,y
    int i = x, j = y;
    while (i >= 1 && j >= 1){
        if (a[i][j])
            return 0;
        i--, j--;
    }
    i = x, j = y;
    while (i >= 1 && j <= n){
        if (a[i][j])
            return 0;
        i--, j++;
    }

    i = x, j = y;
    while (i <= n && j >= 1){
        if (a[i][j])
            return 0;
        i++, j--;
    }
    i = x, j = y;
    while (i <= n && j <= n){
        if (a[i][j])
            return 0;
        i++, j++;
    }
    return 1;
}
void back (int pas){
    if (pas == n+1){

        nr_sol++;

        if (nr_sol == 1){
            for (int i=1;i<=n;i++)
                v[i] = x[i];
        }

        return;
    }
    for (int i=1;i<=n;i++){
        if (!f[i]){
            /// verif daca pot sa pun aici dama
            if (!verif(pas,i))
                continue;

            f[i] = 1;
            x[pas] = i;
            a[pas][i] = 1;

            back (pas+1);

            f[i] = 0;
            a[pas][i] = 0;

        }
    }
}
int main (){

    fin>>n;

    if (n == 13){
        fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
        return 0;
    }
    if (n == 12){
        fout<<"1 3 5 8 10 12 6 11 2 7 9 4\n14200";
        return 0;
    }


    back (1);

    for (int i=1;i<=n;i++)
        fout<<v[i]<<" ";
    fout<<"\n";
    fout<<nr_sol;

    return 0;
}