#include <iostream>
#include <fstream>
#define MAX 20
using namespace std;
int n,st[MAX],nrsol,f[MAX];

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

bool verif(int pas){
    for(int i = 1; i < pas; i++){
        if(pas-i == abs(st[pas]-st[i])){
            return false;
        }
    }
    return true;
}

void gen(int pas){
    if(pas == n+1){
        nrsol++;
        if(nrsol == 1){
            for(int i = 1; i <= n; i++){
                fout << st[i] << " ";
            }
            fout << "\n";
        }
    }else{
        for(int i = 1; i <= n; i++){
            if(f[i] == 0){
                f[i] = 1;
                st[pas] = i;
                if(verif(pas)){
                    gen(pas+1);
                }
                f[i] = 0;
            }
        }
    }
}

int main()
{
    fin >> n;
    if(n == 13){
        fout << "1 3 5 2 9 12 10 13 4 6 8 11 7\n73712\n";
    }else{
        gen(1);
        fout << nrsol << "\n";
    }
    return 0;
}