#include <fstream>

using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int a[13],b[13],d1[22],d2[22],var,n,i;
bool ok;
void dame(int p)
{
    if(p>0)
    {for(int i=1;i<=n;i++)
    if(b[i]==0&&d1[n-p+i]==0&&d2[2*n-p-i+1]==0)
    {
        b[i]=1;
        d1[n-p+i]=1;
        d2[2*n-p-i+1]=1;
        if(ok==0)
            a[p]=i;
        dame(p-1);
        b[i]=0;
        d1[n-p+i]=0;
        d2[2*n-p-i+1]=0;
    }}
    else
    {
        ok=1;
        var++;
    }
}
int main()
{
    fin>>n;
    dame(n);
    for(i=n;i>0;i--)
        fout<<a[i]<<" ";
    fout<<"\n"<<var;
    return 0;
}