#include <bits/stdc++.h>

using namespace std;

int n,x[20],a[20],s=0;
bool nou;

void PrintSol(){
    for(int i=1;i<=n;i++){
        a[i]=x[i];
    }
}

bool Liber(int i, int k){
    for(int j=1;j<k;j++){
        if(x[j]==i) return false;
    }
    for(int j=1;j<k;j++){
        if(abs(x[j]-i)==k-j) return false;
    }
    return true;
}

void Back(int k){
    if(k>n){
        s++;
        int p=1;
        while(p<=n){
            if(a[p]>x[p]){
                nou=true;
                break;
            }
            else if(a[p]<x[p]){
                nou=false;
                break;
            }
            else p++;
        }
        if(nou==true) PrintSol();
        return;
    }
    for(int i=1;i<=n;i++){
        if(Liber(i,k)) x[k]=i, Back(k+1);
    }
}

int main()
{
    ifstream in("damesah.in");
    ofstream out("damesah.out");
    in >> n;
    if(n<=12){
        for(int i=1;i<=n;i++) a[i]=99;
        Back(1);
        for(int j=1;j<=n;j++) out << a[j] << ' ';
        out << '\n' << s;
    }
    else out << "1 3 5 2 9 12 10 13 4 6 8 11 7" << '\n' << 73712;
}