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

using namespace std;

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

int n, v[NMax], sol;

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

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

/// k e nivelul backtracking-ululi = echivalent cu linia
/// j e coloana
void solve(int k){
    for(int i = 1; i <= n; ++i){
        v[k] = i;
        if(valid(v[k], k) == true){
            if(k == n){
                sol++;
                if(sol == 1)
                    print();
            }
            else solve(k + 1);
        }
    }
        return;
}

int main(){

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