#include <fstream>

using namespace std;

ifstream be("damesahin.txt");
ofstream ki("damesahout.txt");

bool isSafe(int tabla[][100], int n, int sor, int oszlop)
{
    //sor szerint
    for(int i=0; i<oszlop; i++){
        if(tabla[sor][i]==1){
            return false;
        }
    }

    //oszlop szerint
    for(int i=0; i<sor; i++){
        if(tabla[i][oszlop]==1){
            return false;
        }
    }

    //bal felső - jobb alsó átló
    for(int i=sor-1, j=oszlop-1; i>=0 && j>=0; i--, j--){
        if(tabla[i][j]==1){
            return false;
        }
    }

    //bal alsó - jobb felső átló
    for(int i=sor-1, j=oszlop+1; i>=0 && j<n; i--, j++){
        if(tabla[i][j]==1){
            return false;
        }
    }

    return true;
}

int szamlalo;

void queen(int tabla[][100], int n, int sor)
{
    if(sor==n){
        szamlalo++;
        if(szamlalo==1){
            for(int i=0; i<n; i++){
                for(int j=0; j<n; j++){
                    if(tabla[i][j]==1){
                        ki<<j+1<<" ";
                    }
                }
            }
        }
        return;
    }

    for(int oszlop=0; oszlop<n; oszlop++){
        if(isSafe(tabla, n, sor, oszlop)){
            tabla[sor][oszlop]=1;
            queen(tabla, n, sor+1);
            tabla[sor][oszlop]=0;
        }
    }
}

int main()
{
    int n;
    be>>n;
    int tabla[100][100]={};

    queen(tabla, n, 0);
    ki<<endl<<szamlalo;

}