#include <bits/stdc++.h>
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int ans;
bool Diagonalap[40],Coloana[40],Digs[40];
void Citire(int &N)
{
    f>>N;
}

void Afisare(int N,int Poz[])
{
    cout<<"Solutia cu numarul "<<ans<<'\n';
    for(int i=1;i<=N;i++,cout<<'\n')
    for(int j=1;j<=N;j++)
    if(j==Poz[i]) cout<<"* ";
    else cout<<"- ";

    cout<<'\n'<<'\n';
}

bool Verif(int Poz[],int line,int column)
{
    for(int i=1;i<line;i++)
    if( column!=Poz[i] &&  abs( line - i ) != abs( column - Poz[i] ) )
    // regina de pe linia i nu se afla pe aceasi coloana cu regina de pe lini 1
    // si nu se afla pe aceasi diagonala
    // tg(alfa)!=45 => (line- i) / ( column - Poz[i] ) == 1
    continue;
    else return false;

    return true;
}

void BKT(int N,int Poz[],int k)
{
    if( k == N + 1 ) // toate cele N regine au fost puse pe tabla
    {
         ans++;
        // Afisare(N,Poz);
        if(ans==1) for(int i=1;i<=N;i++) g<<Poz[i]<<' ';
        return;
    }
    for(int i=1;i<=N;i++) // caut o coloana optima pentru amplasare
    if( Coloana[i]==0 && Diagonalap[(k-i>=0)?(k-i):(N-k+i)]==0 && Digs[(N-k+1-i)>=0?(N-k+1-i):k+i-1]==0 )
    {
        Poz[k]=i;
        Coloana[i]=1;
        Diagonalap[(k-i>=0)?(k-i):(N-k+i)]=1;
        Digs[(N-k+1-i)>=0?(N-k+1-i):k+i-1]=1;
        BKT(N,Poz,k+1);
        Coloana[i]=0;
        Digs[(N-k+1-i)>=0?(N-k+1-i):k+i-1]=0;
        Diagonalap[(k-i>=0)?(k-i):(N-k+i)]=0;
    }
}

int main()
{
    int N;
    Citire(N);
    int Poz[N+1];
    BKT(N,Poz,1);
g<<'\n'<<ans;
    return 0;
}