#include <bits/stdc++.h>
using namespace std;
int A[20][20], D[20], n, V[20], rs;

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

void back(int k){

    for(int i=1; i<k-1; i++){
        if(A[i][D[k-1] + (k-1-i)] == 1 || A[i][D[k-1] - (k-1-i)] == 1){
            // cout << "se elimina pasul " << k-1 << endl;
            return;
        }
    }

    if(k == n+1){
        rs++;
        if(rs == 1){
            for(int i=1; i<=n; i++){
                fout << D[i] << ' ';
            }
            fout << endl;
        }
        return;
    }

    for(int i=1; i<=n; i++){
        if(!V[i]){
            V[i] = 1;
            D[k] = i;
            A[k][D[k]] = 1;
            back(k+1);
            V[i] = 0;
            A[k][D[k]] = 0;
        }
    }
}

int main(){
    fin >> n;
    back(1);
    fout << rs << endl;
}