#include <bits/stdc++.h>

using namespace std;

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

int v[20];
int n,ok = 0,c = 0;

bool eok(int k){
    int i;
    for(i = 1; i < k; i++){
        if(v[i] == v[k]){
            return 0;
        }
    }
    for(i = 1; i < k; i++){
        if(v[k] - (k-i) == v[i]){
            return 0;
        }
    }
    for(i = 1; i < k; i++){
        if(v[k] + (k-i) == v[i]){
            return 0;
        }
    }
    return 1;
}

void backtr(int k){
    int i;
    for(i = 1; i <= n; i++){
        v[k] = i;
        if(eok(k)){
            if(k < n){
                backtr(k+1);
            }else{
                if(!ok){
                    ok = 1;
                    for(int j = 1; j <= n; j++){
                        fout<<v[j]<<' ';
                    }
                    fout<<'\n';
                }
                c++;
            }
        }
    }
}

int main()
{
    fin>>n;
    backtr(1);
    fout<<c<<'\n';
    return 0;
}