#include <fstream>
#include <iostream>
#define NMax 17

using namespace std;

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

int n, v[NMax], sol, use[NMax];

void print(){
    for(int i = 1; i <= n; ++i)
        fout << v[i] << " ";
    fout << '\n';
}

bool valid(int k){
    for(int i = 1; i < k; ++i){
        if(v[k] - v[i] == k - i || v[i] - v[k] == k - i)
            return false;
    }
    return true;
}

void solve(int k){
    for(int i = 1; i <= n; ++i){
        v[k] = i;
        use[i]++;
        if(use[i] == 1)
        if(valid(k) == true){
            if(k == n){
                sol++;
                if(sol == 1)
                    print();
            }
            else solve(k + 1);
        }
        use[i]--;
    }
    return;
}

int main(){

    fin >> n;
    solve(1);
    fout << sol;
    fin.close();
    fout.close();
    return 0;
}