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