#include <iostream>
#include <fstream>
#define VM 20

using namespace std;

int m[VM][VM];

int col[VM];
int d1[VM];
int d2[VM];
int lin[VM];
int sol[VM];

int k = 0, ok = 1;

void Asezare(int i, int j, int x, int n){
    ///Daca x = 1 plasam dama,
    ///Daca x =-1 luam   dama
    m[i][j] += x;
    lin[i] += x;
    col[j] += x;
    d1[i - j + n] += x;
    d2[i + j] += x;
}

bool Verificare(int i, int j, int n){
    ///Daca e libera pozitia
    return (lin[i] == 0 && col[j] == 0 && d1[i - j + n] == 0 && d2[i + j] == 0);
}

void Dame(int i, int j, int n){
    ///Conditie de oprire
    if(i > n){
        if(ok){
            int a = 1;
            for(int i = 1 ; i <= n ; ++i)
                for(int j = 1 ; j <= n ; ++j)
                    if(m[i][j] == 1){
                        sol[a] = j;
                        ++a;
                    }
        }
        ok = 0;
        ++k;
        return;
    }
    if(j > n){
        if(lin[i] == 1)
            Dame(i + 1 , 1 , n);
    }
    else{
        if(Verificare(i , j , n)){
            ///Daca pozitia e libera punem dama
            Asezare(i , j , 1 , n);
            Dame(i + 1 , 1 ,n);
            ///Luam dama
            Asezare(i , j , -1 , n);
        }
        Dame(i , j + 1 , n);
    }
}

ifstream f("damesah.in");
ofstream g("damesah.out");

int main()
{
    int n;
    f>>n;
    Dame(1 , 1 , n);
    for(int i = 1 ; i <= n ; ++i)
        g<<sol[i]<<" ";
    g<<'\n';
    g<<k;
    return 0;
}