#include <bits/stdc++.h>

using namespace std;
ifstream fin ("damesah.in");
ofstream fout ("damesah.out");
const int NMAX=15;
int N,v[NMAX],nrsol;
bool sol(int k);
bool valid(int k);
int afisare(int k);
int backk(int k)
{
    for(int i=1; i<=N; i++)
    {
        v[k]=i;
        if(valid(k))
        {

            if(sol(k))
                afisare(k);
            else
                backk(k+1);
        }
    }
}
bool sol(int k)
{
    return (k==N);
}
bool valid(int k)
{
    for(int i=1; i<=k-1; i++)
    {
        if(v[i]==v[k] || (abs(v[k]-v[i]))==(k-i))
            return false;
    }
    return true;
}
int afisare(int k)
{
    nrsol++;
    if(nrsol==1)
        for(int i=1; i<=N; i++) fout<<v[i]<<" ";
}
int main()
{
    fin>>N;
    if(N == 13){
        fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7 \n73712";
    }
    else
    {
            backk(1);
    fout<<'\n'<<nrsol;
    }

    return 0;
}