# include <fstream>
# include <set>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
set<int> myset;
set<int>::iterator it;
int fd1[30],fd2[30],next[30],last[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=next[0];i<n+1;i=next[i]){
        if(fd1[poz-i+n+1]==0&&fd2[poz+i]==0){
            fd1[poz-i+n+1]=1;
            fd2[poz+i]=1;
            v[poz]=i;
            next[last[i]]=next[i];
            last[next[i]]=last[i];
            back(poz+1);
            next[last[i]]=i;
            last[next[i]]=i;
            fd1[poz-i+n+1]=0;
            fd2[poz+i]=0;
        }
    }
}
int main () {
    fin>>n;
    for(int i=0;i<=n;i++)
        next[i]=i+1;
    for(int i=n+1;i>=1;i--)
        last[i]=i-1;
    sol[1]=n+1;
    back(1);
    afisare(sol);
    fout<<nr<<"\n";
    return 0;
}