#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,nr,st[20],fr1[100],fr2[100],fr[100];
void _back(int poz)
{
    if(poz==n+1)
    {
        if(nr==0)
            for(int i=1;i<=n;i++)
                g<<st[i]<<" ";
        nr++;
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(fr[i])
            continue;
        if(fr1[i-poz+n])
            continue;
        if(fr2[i+poz])
            continue;
        fr[i]=1;
        fr1[i-poz+n]=1;
        fr2[i+poz]=1;
        st[poz]=i;
        _back(poz+1);
        fr[i]=0;
        fr1[i-poz+n]=0;
        fr2[i+poz]=0;
    }
}
int main()
{
    f>>n;
    _back(1);
    g<<'\n'<<nr;
    return 0;
}