#include <fstream>
#include <cmath>
using namespace std;
int a[100];
int f[100];
int n,sol;
ifstream fin("damesah.in");
ofstream fout("damesah.out");

int verif (int pas) {
    for (int i=1;i<pas;i++) {
        if (abs(a[i]-a[pas])==abs(i-pas)) return 0;
    }
    return 1;
}

void backtrack (int pas) {
    if (pas==n+1) {
        if (sol==0) {
            for (int i=1;i<=n;i++) fout<<a[i]<<" ";
            fout<<"\n";
        }
        sol++;
    }
    else {
        for (int i=1;i<=n;i++) {
            a[pas]=i;
            if (f[i]==0&&verif(pas)) {
                f[i]=1;
                backtrack(pas+1);
                f[i]=0;
            }
        }
    }
}

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