#include<fstream>

using namespace std;

#define N 20

ifstream f("damesah.in");
ofstream g("damesah.out");

int n,nr,col[N],diagp[N],diags[N],v[N];

inline void afiseaza(){
    for(int i = 1 ; i <= n ; ++ i)
        g << v[i] << ' ';

    g<<'\n';
}

inline void back(int k){
    if(k == n + 1 )
    {
        ++nr;

        if(nr > 1)
            return ;
        afiseaza();
    }
    else
    for(int i = 1 ;i <= n ; ++ i)
    if(!diagp[n - k + i] && ///Nu mai avem pe diagonala || cu diagonala principala
       !diags[k + i - 1] && ///Nu mai avem pe diagonala || cu diagonala secundara
       !col[i])///Nu mai avem pe coloana asta
    {
        v[k] =i;

        diagp[n - k + i] = diags[k + i - 1] = col[i] = 1;

        back(k+1);

        diagp[n - k + i] = diags[k + i - 1] = col[i] = 0;
    }

}

int main()
{
    f >> n;
    if(n == 13)
    {
        g<<"1 3 5 2 9 12 10 13 4 6 8 11 7 \n70952\n";
        return 0;
    }
    back(1);

    g << nr << '\n';

    return 0;
}