#include <fstream>
#define DIM 14
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,sol,v[DIM];
bool c[DIM],p[2*DIM],s[2*DIM];

void backtrack(int k) {
    if (k==n+1) {
        sol++;
        if (sol==1)
            for (int i=1;i<=n;i++)
                fout<<v[i]<<" ";
    }
    else
        for (int i=1;i<=n;i++) {
            v[k]=i;
            if (c[i]==0 && p[i-k+n]==0 && s[i+k]==0) {
                c[i]=1;
                p[n+i-k]=1;
                s[i+k]=1;
                backtrack(k+1);
                c[i]=0;
                p[n+i-k]=0;
                s[i+k]=0;
            }
        }
}

int main() {
    fin>>n;
    backtrack(1);
    fout<<"\n"<<sol;
    return 0;
}