#include <bits/stdc++.h>

using namespace std;

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

int n,ok,col[15],diag[30],sdiag[30],v[15];

int getd(int l,int c){
    return n-l+c;
}

int getsd(int l,int c){
    return 2*n-c-l;
}

void afisare(){
    if(ok==0)
        for(int i=1; i<=n; i++)
            g<<v[i]<<' ';
    ok++;
}

void backt(int k)
{
    for(int i=1; i<=n; i++)
        if(col[i]==0 and diag[getd(k,i)]==0 and sdiag[getsd(k,i)]==0)
        {
            v[k]=i;
            if(k==n)
                afisare();
            else
            {
                col[i]=diag[getd(k,i)]=sdiag[getsd(k,i)]=1;
                backt(k+1);
                col[i]=diag[getd(k,i)]=sdiag[getsd(k,i)]=0;
            }
        }
}

int32_t main()
{
    f>>n, backt(1), g<<'\n'<<ok;
    return 0;
}