//Problema regine - varena
// queen(k,st[k])
#include<fstream>
#include<bitset>
using namespace std;
int st[10];
bitset<20> col,ld,rd;
int n,i,k,nrsol;

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

inline void init(){
    st[k]=0;
}
int succesor(){
    if (st[k]<n){
        st[k]++;
        return 1;
    }
    return 0;
}
int valid(){
    if (col[st[k]]==1 || ld[st[k]-k+n-1]==1 || rd[k+st[k]]==1)
        return 0;
    else{
        col[st[k]]=1;
        ld[st[k]-k+n-1]=1;
        rd[k+st[k]]=1;
        return 1;
    }
}
int solutie(){
    if (k==n) return 1;
    return 0;
}
void afis(){
    int j;
    nrsol++;
    if (nrsol<=1) {
        for (j=1; j<=n; j++)
            g<<st[j]<<' ';
        g<<'\n';
    }
}
void backt(){
    int es,ev;
    k=1; init();
    while (k>0){
        do{
            es=succesor();
            if (es)
                ev=valid();
        }while (es && !ev); //pana cand gasesc un succesor valid
        if (es) //daca am gasit
            if (solutie()){
                afis();
                col[st[k]]=ld[st[k]-k+n-1]=rd[k+st[k]]=0;
            }
            else {
                k++;
                init();
            }
        else{
            k--;
            col[st[k]]=ld[st[k]-k+n-1]=rd[k+st[k]]=0;
        }
    }
}

int main(){
    f>>n;
    backt();
    g<<nrsol<<'\n';
    f.close();
    g.close();
    return 0;
}