#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)
    {
        if(nr == 0)
            afiseaza();

        ++nr;

        return ;
    }

    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] = 1;
        diags[k + i - 1] = 1;
        col[i] = 1;

        back(k+1);

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

}

int main()
{
    f >> n;

    back(1);

    g << nr << '\n';

    return 0;
}