#include <iostream>
#include <fstream>
using namespace std;

ofstream fout("damesah.out");

int map[100][100]; // aparitii dame coloane, linii si diagonale
int n, vsol[100];
unsigned long long sum=0;

void damafill(int vi, int i, int val){
    int ii=0;
    if (val==0)
        ii=vi+1;

    for (int o=0; o<n; ++o){
        if (map[vi][o]==ii)
            map[vi][o]=val; //linie
        if (map[o][i]==ii)
            map[o][i]=val; //coloana
    }
    //diagonale
    for (int o=1; vi-o>=0 && i-o>=0; ++o)
        if (map[vi-o][i-o]==ii)
            map[vi-o][i-o]=val;  
    for (int o=1; i+o<n && vi-o>=0; ++o)
        if (map[vi-o][i+o]==ii)
            map[vi-o][i+o]=val;
    for (int o=1; vi+o>=0 && i-o>=0; ++o)
        if (map[vi+o][i-o]==ii)
            map[vi+o][i-o]=val;  
    for (int o=1; i+o<n && vi+o<n; ++o)
        if (map[vi+o][i+o]==ii)
            map[vi+o][i+o]=val;
}

void Backt(int vi){
    for (int i=0; i<n; ++i){
        vsol[vi]=i;
        if (map[vi][i]==0){
            if (vi!=n-1){
                 //creare dama negat pe lini, coloana si diagonala
                damafill(vi,i,vi+1);
            /* cout<<vi<<' '<<i<<'\n';
            for (int j=0; j<n; ++j){
                for (int k=0; k<n; ++k)
                    cout<<map[j][k]<<' ';
                cout<<'\n';
                }
            cout<<'\n';
            */
                Backt(vi+1);
            } else{
                if (sum==0)
                    for (int o=0; o<n; ++o)
                        fout<<vsol[o]+1<<' ';
                ++sum;
            }
        }
    }
    //resetare dame de pe linie, coloana si diagonala
    //cout<<vsol[vi-1]<<'\n';
    if (vi)
        damafill(vi-1,vsol[vi-1],0);
}

int main(){
    ifstream fin("damesah.in");
    fin>>n; 
    int vi=0;
    Backt(vi);
    fout<<'\n'<<sum;
    return 0;
}