#include <fstream>

using namespace std;

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

int sol,n;
int col[50],diag1[50],diag2[50],v[50];

void back(int k) {
    if(k-1==n) {
        if(sol==0) {
            for(int i=1;i<=n;i++)
                g<<v[i]<<" ";
            g<<"\n";
        }
        sol++;
        return;
    }
    for(int i=1;i<=n;i++)
        if(col[i]==0 && diag1[i-k+n]==0 && diag2[2*n-i-k+1]==0){
            col[i]=diag1[i-k+n]=diag2[2*n-i-k+1]=1;
            v[k]=i;
            back(k+1);
            col[i]=diag1[i-k+n]=diag2[2*n-i-k+1]=0;
        }
}

int main() {
    f>>n;
    back(1);
    g<<sol<<"\n";
    return 0;
}