#include    <iostream>
#include    <fstream>
#include    <cstdlib>

using namespace std;

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

int n,s[14],cnt,viz[14];

bool ok(int pas, int v)
{
    if(pas==1) return true;

    for(int i=1;i<pas;i++)
    if(abs(pas-i)==abs(s[i]-v)) // verifica diagonalele
      return false;
    return true;
}

void afisare()
{
    if(!cnt)
    for(int i=1;i<=n;i++)
    fout<<s[i]<<' ';
    cnt++;
}

void back(int pas)
{
    if(pas>n)
    afisare();
        else
    {
        for(int i=1;i<=n;i++)
          if(!viz[i] && ok(pas,i)){
          viz[i]=1;
          s[pas]=i;
          back(pas+1);
          viz[i]=0;
          }
    }
}

int main()
{
    fin>>n;
    back(1);
    fout<<'\n'<<cnt;
}