#include <bits/stdc++.h>
using namespace std;
ifstream fin("permutari.in");
ofstream fout("permutari.out");
int f[14];
int v[14];
int f1[30];
int f2[30];
int n;
int cnt;
int nr=0;
void perm(int x) {
    if(x>n) {
        if(nr==0) {
            for(int i=1;i<=n;i++) fout<<v[i]<<" ";
            fout<<'\n'; }
        nr++;
        x--;
        return;
    }
    cnt=0;
    for(int i=1;i<=n;i++) {
        if(f[i]==0 && f1[x+i]==0 && f2[x-i+14]==0) {
            v[x]=i;
            f[i]=1;
            f1[x+i]=1;
            f2[x-i+14]=1;
            cnt=1;
            perm(x+1);
            f[i]--;
            f1[x+i]--;
            f2[x-i+14]--;
        }
    }
    if(cnt==0) return;
}

int main()
{
    fin>>n;
    perm(1);
    fout<<nr;

    return 0;
}