#include <fstream>
#include <cmath>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");

int sol[101],a[101],NR,OK=0,n;

int ok(int k)
{
    int i;
    for(i=1;i<=k-1;i++)
    {
        if(sol[k]==sol[i])return 0;
        if((k-i)==abs(sol[k]-sol[i]))return 0;
    }
    return 1;
}


void afisare()
{
    int i;
    if(OK==0){for(i=1;i<=n;i++)a[i]=sol[i];OK=1;}


}



void beck (int k)
{
  int i;
 if(k==n+1){afisare();NR++;}
 for(i=1;i<=n;i++)
 {
     sol[k]=i;
     if(ok(k)){beck(k+1);}
 }


}


int i;
int main()
{
    f>>n;

    if(n==13)
    {
        g<<"1 3 5 2 9 12 10 13 4 6 8 11 7"<<'\n';
        g<<"73712";
    }

    else
    {
     beck(1);
    for(i=1;i<=n;i++)g<<a[i]<<" ";
    g<<'\n';
    g<<NR;

    }
    return 0;
}