#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,i,a[30],b[30],c[30],nrsol,v[30];
void bkt(int);
int main()
{
    f>>n;
    bkt(1);
    g<<"\n"<<nrsol<<"\n";
    return 0;
}
void bkt(int i)
{
    if(i==n+1)
    {
        if(!nrsol)
        for(int k=1;k<=n;k++)
            g<<v[k]<<" ";
        nrsol++;return;
    }
    for(int j=1;j<=n;j++)
        if(a[i+j-1]+b[n-i+j]+c[j]==0)
        {
            v[i]=j;
            a[i+j-1]=1;
            b[n-i+j]=1;
            c[j]=1;
            bkt(i+1);
            a[i+j-1]=0;
            b[n-i+j]=0;
            c[j]=0;
        }
}