#include <iostream>
#include <math.h>
#include<fstream>
using namespace std;


int x[13];
int solutie[13], nrSolutii, n, col[15];



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

bool valid(int k){
    for (int i = 1; i < k; ++i)        if ( k - i == fabs(x[k] - x[i])){
            return false;
    }
    return true;
}

void back(int k){

    if (k==n+1) {
                  ++nrSolutii;
                  if (nrSolutii==1) afisare();

                }
    else
     for (int i=1; i<=n; i++)
        if (!col[i])
        {
            x[k]=i;col[i]=1;
            if (valid(k)) back(k+1);
            col[i]=0;
        }
}

int main() {
    ofstream o("damesah.out");
    ifstream f("damesah.in");

    f >> n;
    back(1);
    for (int i = 1; i <= n; ++i){
        o << solutie[i] << " ";
    }
    o << '\n';
    o << nrSolutii;
    return 0;
}