#include <iostream>
#include <fstream>
#define Nmax 15
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int N,pozd[Nmax],r[Nmax],d1[2*Nmax],d2[2*Nmax],csol;
void read()
{
    fin>>N;
}
int Abs(int x)
{
    if(x>=0)
        return x+1;
    return -x+N;
}
void Back(int dama)
{
    if(dama>N)
    {
        csol++;
        if(csol<2)
        {
            for(int i=1;i<=N;i++)
                fout<<pozd[i]<<" ";
        }
    }
    else
    {
        for(int i=1;i<=N;i++)
        {
            if(!r[i])
            {
                if(!(d1[Abs(i-dama)] || d2[Abs(N-dama+1-i)]))
                {
                    r[i]=1;
                    d1[Abs(i-dama)]=1;
                    d2[Abs(N-dama+1-i)]=1;
                    pozd[dama]=i;
                    Back(dama+1);
                    r[i]=0;
                    d1[Abs(i-dama)]=0;
                    d2[Abs(N-dama+1-i)]=0;
                }
            }
        }
    }
}
void solve()
{
    Back(1);
    fout<<"\n"<<csol<<"\n";
}
int main()
{
    read();
    solve();
    return 0;
}