#include <fstream>
#include <cmath>
#include <climits>
#define dim 15
using namespace std;
int a[dim];
int f[dim];
int Sol[dim];
int i,n,sol;

int verif (int pas) {
    for (int i=1;i<pas;i++) {
        if (abs(a[pas]-a[i])==pas-i) return 0;
    }
    return 1;
}

void backtrack (int pas) {
    if (pas==n+1) {
        sol++;
        if (sol==1) {
            for (int i=1;i<=n;i++) {
                Sol[i]=a[i];
            }
        }
    }
    else {
        for (int i=1;i<=n;i++) {
            if (f[i]==0) {
                f[i]=1;
                a[pas]=i;
                if (verif(pas)) {
                    backtrack(pas+1);
                }
                f[i]=0;
            }
        }
    }
}

int main() {
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    fin>>n;
    backtrack(1);
    for (i=1;i<=n;i++) {
        fout<<Sol[i]<<" ";
    }
    fout<<"\n";
    fout<<sol;
    return 0;
}