#include <fstream>

using namespace std;

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

int x[14],n,nr,viz[14],diagsec[30],diagpr[30];
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;
}