#include <fstream>

using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");

int n;
int lin[15],dap[30],das[30];
int rem[15],sol[15],nr;

void find_all(int poz=1)
{
    if(poz>n)
    {
        nr++;
        if(nr==1)
            for(int i=1;i<=n;i++)
                sol[i]=rem[i];

        return;
    }

    for(int i=1;i<=n;i++)
    {
        if(lin[i] || dap[n-i+poz] || das[i+poz-1])
            continue;

        lin[i]=dap[n-i+poz]=das[i+poz-1]=1;
        rem[poz]=i;

        find_all(poz+1);

        lin[i]=dap[n-i+poz]=das[i+poz-1]=0;
    }
}

int main()
{
    cin>>n;

    find_all();

    for(int i=1;i<=n;i++)
        cout<<sol[i]<<' ';

    cout<<'\n'<<nr;

    return 0;
}