#include <fstream>
using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
int n,i,nr,v[101],c[101],d1[101],d2[101];

int back(int niv){
    if(niv>n)
        if(nr==0){
            for(int i=1;i<=n;i++)
                fout<<v[i]<<" ";
            fout<<"\n";
            ++nr;
        }
        else
            ++nr;
    for(int i=1;i<=n;i++){
        if(c[i]==0 && d1[i+niv]==0 && d2[i-niv+n+1]==0){
            v[niv]=i;
            c[i]=1;
            d1[i+niv]=1;
            d2[i-niv+n+1]=1;
            back(niv+1);
            c[i]=0;
            d1[i+niv]=0;
            d2[i-niv+n+1]=0;
        }
    }

}


int main(){
    fin>>n;
    back(1);
    fout<<nr;
}