#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int nr;
int S[16];
int diag1[35],diag2[35];
int C[16];

void bkt(int,int);
void afisare(int);
bool safe(int,int,int);

int main()
{
 int n;
 fin>>n;
 bkt(1,n);
 fout<<nr;
 return 0;
}

void bkt(int i,int n)
{int j;
 if(i==n+1)
    {if(nr==0) afisare(n);
    nr++;
    return;
    }

 for(j=1;j<=n;j++)
    if(safe(i,j,n))
     {C[j]=1; S[i]=j;
      if(i>=j) diag1[n-i+j]=1;
      else diag1[n+j-i]=1;
      diag2[i+j-1]=1;

      bkt(i+1,n);

      C[j]=0;
      if(i>=j) diag1[n-i+j]=0;
      else diag1[n+j-i]=0;
      diag2[i+j-1]=0;
     }
}

void afisare(int n)
{int i;
 for(i=1;i<=n;i++) fout<<S[i]<<" ";
 fout<<'\n';
}

bool safe(int i, int j,int n)
{
 if(C[j]) return 0;
 if(i>=j) {if(diag1[n-i+j]==1)return 0;}
 else if(diag1[n+j-i]==1)return 0;
 if(diag2[i+j-1]==1) return 0;
 return 1;
}