#include <fstream>
#include <string.h>
#define NMax 15
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, col[NMax], sol[NMax], nrsol, ok;
bool c[NMax], ds[NMax*2], dp[NMax*2];
void back(int k)
{
    if (k==n+1) {
        if (ok==0)
            for (int i=1; i<=n; i++)
                sol[i]=col[i];
        nrsol++;
        ok=1;
        return ;
    }
    for (int i=1; i<=n; i++) {
        if (c[i]==0 && ds[i+k]==0 && dp[n-i+1]==0) {
            col[k]=i;
            c[i]=1;
            ds[i+k]=1;
            dp[n-i+1]=1;
            back(k+1);
            c[i]=0;
            ds[i+k]=0;
            dp[n-i+1]=0;
        }
    }
}
int main()
{
    f>>n;
    back(1);
    for (int i=1; i<=n; i++)
        g<<sol[i]<<" ";
    g<<"\n";
    g<<nrsol;
    return 0;
}