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

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

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
    {
        //Afisare(N,Poz);
        ans++;
        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( Verif(Poz,k,i) )
    {
        Poz[k]=i;
        BKT(N,Poz,k+1);
    }
}

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

    return 0;
}