#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;
    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;
}