# include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int fd1[30],fd2[30],f[30],v[30],sol[30],n,nr;
bool comp(int a[],int b[]){
    for(int i=1;i<=n;i++){
        if(a[i]<b[i])
            return 0;
        if(a[i]>b[i])
            return 1;
    }
    return 0;
}
void artibuie(int a[],int b[]){
    for(int i=1;i<=n;i++)
        a[i]=b[i];
}
void afisare(int a[]){
    for(int i=1;i<=n;i++)
        fout<<a[i]<<" ";
    fout<<"\n";
}
void back(int poz){
    if(poz==n+1){
        nr++;
        if(comp(sol,v))
            artibuie(sol,v);
        return;
    }
    for(int i=1;i<=n;i++){
        if(fd1[poz-i+n+1]==0&&fd2[poz+i]==0&&f[i]==0){
            fd1[poz-i+n+1]=1;
            fd2[poz+i]=1;
            f[i]=1;
            v[poz]=i;
            back(poz+1);
            fd1[poz-i+n+1]=0;
            fd2[poz+i]=0;
            f[i]=0;
        }
    }
}
int main () {
    fin>>n;
    sol[1]=n+1;
    back(1);
    afisare(sol);
    fout<<nr<<"\n";
    return 0;
}