#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
#define N 13
int cntr;
int n;
bitset <maxn> col;
bitset <2*maxn> dp , ds ;
pair < int , int  > regina[N];

void afisare()
{
    cntr++;
    if( cntr == 1 )
    {
        for( int i = 1 ; i <= n ; ++i )
            fout << regina[i].second << ' ';
        fout << '\n' ;
    }
}

void backtracking( int linie )
{
    if( linie == n+1 )
    {
        afisare();
        return ;
    }
    for( int coloana = 1 ; coloana <= n ; ++coloana)
    {
        if( !col[coloana] && !dp[ linie + coloana - 1]
           && !ds[ linie + n - coloana] )
        {
            regina[linie] = make_pair( linie , coloana );

            col[coloana] = 0 ;
            dp[ linie + coloana - 1 ] = 0 ;
            ds[ linie + n - coloana ] = 0;

            backtracking( linie + 1 );

            col[coloana] = 0 ;
            dp[ linie + coloana - 1 ] = 0 ;
            ds[ linie + n - coloana ] = 0;
        }
    }
}

int main()
{
    fin >> n ;
    backtracking( 1 );
    fout << cntr ;
    return 0;
}