#include <fstream>

using namespace std;
int n,c[100],nr,D1[200],D2[200],sol[200];
ifstream fin("damesah.in");
ofstream fout("damesah.out");
void afis()
{
    for(int i=1;i<=n;i++)
        fout<<sol[i]<<" ";
    fout<<"\n";
}
void back(int k)
{int ok,i,j;
    if(k>n){
        if(nr==0)
            afis();
        nr++;
    }
    else{
        for(i=1;i<=n;i++)
            if(!c[i] && !D1[k+i] && !D2[n+k-i]){
                c[i]=1;
                D1[k+i]=1;
                D2[k-i+n]=1;
                sol[k]=i;
                back(k+1);
                c[i]=0;
                D1[k+i]=0;
                D2[k-i+n]=0;
            }
    }

}
int main()
{
    fin>>n;
    back(1);
    fout<<nr;
    fin.close();fout.close();
    return 0;
}