#include <bits/stdc++.h>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,v[15],up[15],sol[15],nr=0,k=1;
bool verif(int x, int i)
{
    for(int j=1; j<x; j++)
    {
        if(abs(j-x)==abs(sol[j]-i))
            return false;
    }
    return true;
}
void bac(int x)
{
    if(x==n+1)
    {
        if(k)
        {
            for(int i=1; i<=n; i++)
            {
                up[i]=sol[i];
            }
            k=0;
        }
        nr++;
        return;
    }
    for(int i=1; i<=n; i++)
    {
        if(!v[i] && verif(x,i))
        {
            sol[x]=i;
            v[i]=1;
            bac(x+1);
            v[i]=0;
        }
    }
}
int main()
{
    in >> n;
    bac(1);
    for(int i=1; i<=n; i++)
    {
        out << up[i] << ' ';
    }
    out << '\n' << nr;
    return 0;
}