#include <bits/stdc++.h>
using namespace std;

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

int n,s[15],rs;
bool c[15],d1[30],d2[30];

void back(int k) {
    if(k==n+1) {
        rs++;
        if(rs==1) {
            for(int i=1;i<=n;i++)
                out<<s[i]<<' ';
            out<<'\n';
        }
        return;
    }

    for(int j=1;j<=n;j++) {
        if(c[j]==0 and d1[k-j+n]==0 and d2[k+j-1]==0) {
            s[k]=j;
            c[j]=d1[k-j+n]=d2[k+j-1]=true;
            back(k+1);
            c[j]=d1[k-j+n]=d2[k+j-1]=false;
        }
    }
}

int main() {
    in>>n;
    back(1);
    out<<rs<<'\n';
    return 0;
}