#include <bits/stdc++.h>

using namespace std;
ifstream in("damesah.in");
ofstream out("damesah.out");
int n,v[15],up[15],dp[50],ds[50],sol[15],nr=0,k=1;
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] && !dp[x-i+n] && !ds[x+i])
        {
            dp[x-i+n]=1;
            ds[x+i]=1;
            sol[x]=i;
            v[i]=1;
            bac(x+1);
            v[i]=0;
            dp[x-i+n]=0;
            ds[x+i]=0;
        }
    }
}
int main()
{
    in >> n;
    bac(1);
    for(int i=1; i<=n; i++)
    {
        out << up[i] << ' ';
    }
    out << '\n' << nr;
    return 0;
}