#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

int x[14],n,nr,viz[14],diagsec[30],diagpr[30];
/*int Test(int k)
{
    int cx=k-1;
    int cy=x[k]-1;
    // cautare dama NORD-VEST
    while( cx>0 && cy>0 )
    {
        if(x[cx]==cy) return 0;
        cx--;
        cy--;
    }

    // cautare dama NORD-EST
    cx=k-1;
    cy=x[k]+1;
    while( cx>0 && cy<=n )
    {
        if(x[cx]==cy) return 0;
        cx--;
        cy++;
    }
 return 1;
}*/
void Afisare()
{
    for(int i=1;i<=n;i++)
        fout<<x[i]<<" ";
}
void Back(int k)
{
    for(int i=1;i<=n;i++)
    {
        if(viz[i]==0 && diagsec[ k + i - 1 ]==0 && diagpr[ k + n - i]==0 )
         {
             x[k]=i;
             viz[i]=1;
             diagsec[k+i-1]=1;
             diagpr[k+n-i]=1;
                if(k==n) {
                          if(nr==0) {Afisare();nr++;}
                          else nr++;
                         }
                else Back(k+1);

         x[k]=0;
         viz[i]=0;
         diagsec[k+i-1]=0;
         diagpr[k+n-i]=0;
         }
    }
}
int main()
{
    fin>>n;
    Back(1);
        fout<<"\n"<<nr;
    return 0;
}