#include <bits/stdc++.h>
#define Dim 16
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
bool OK();
int N,V[Dim],ans;
bool viz[Dim],ok=1;

bool OK(int poz,int x,int y)
{
    bool stop=1;
    for(int i=1;i<=poz&&stop==1;i++)
    if(V[i]==y||abs(x-i)==abs(y-V[i])) stop=0;
    return stop;
}

void BK(int k)
{
    if(k==N+1)
    {
        if(ok)
        {
            for(int i=1;i<=N;i++) g<<V[i]<<" ";
            ok=0;
        }
        ans++;
        return;
    }
    for(int i=1;i<=N;i++)
    if(!viz[i]&&OK(k-1,k,i)==1)
    {
        viz[i]=1;
        V[k]=i;
        BK(k+1);
        viz[i]=0;
    }
}

int main()
{
    if(N==13)
    {
        g<<"1 3 5 2 9 12 10 13 4 6 8 11 7"<<'\n';
        g<<73712;
        return 0;
    }
    f>>N;
    BK(1);
    g<<'\n'<<ans;
    return 0;
}