#include <fstream>
#include <cmath>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n, x[15];
bool ok=0;
int nr=0;
bool valid(int k)
{
    for (int i=1; i<k; ++i)
        if (x[k]==x[i] || k-i==abs(x[k]-x[i])) return false;
    return true;
}
void afis()
{
    for (int i=1; i<=n; ++i)
            fout<<x[i]<<' ';
}
void bt(int k)
{
    if (k<=n)
        for (int i=1;  i<=n; ++i)
        {
            x[k]=i;
            if (valid(k)) bt(k+1);
        }
        else if (ok==0) afis(), ok=1, nr++;
        else nr++;
}
int main()
{
   fin>>n;
   bt(1);
   fout<<'\n'<<nr;
    return 0;
}