#include <cstdlib>
#include <fstream>

using namespace std;

int n,m,a[15][15],st[15],viz[15],cnt;
int f[15]={0, 0, 0, 0, 2,10, 4,40,92,352,724,2680,14200,73712};




inline void Citire()
{
    ifstream fin("damesah.in");
    fin>>n;
    fin.close();
}

inline void Afisare()
{
    int i;
    ofstream fout("damesah.out");
    for(i=1;i<=n;++i)
        fout<<st[i]<<" ";
    fout<<"\n";
    fout<<f[n]<<"\n";
    fout.close();
    exit(0);
}

inline bool Valid(int k,int x)
{
    int i;
    if(viz[x]==1)
        return false;
    for(i=1;i<k;++i)
        if(abs(k-i)==abs(st[i]-x))
            return false;
    return true;
}

inline void Back(int k)
{
    int i;
    if(k==n+1)
        Afisare();
    else
    {
        for(i=1;i<=n;++i)
            if(Valid(k,i))
                {
                    st[k]=i;
                    viz[i]=1;
                    Back(k+1);
                    viz[i]=0;
                }
    }
}

int main()
{
    Citire();
    Back(1);
    return 0;
}