#include <fstream>
using namespace std;
ofstream fout ("damesah.out");
ifstream fin ("damesah.in");
int n,rsp,v[15],d1[30],d2[30],st[15];
void tipar()
{
    rsp++;
    if( rsp == 1 )
        for( int i = 1 ; i <= n ; i++ )
            fout<<st[ i ]<<" ";
}
void backtr( int niv )
{
    if( niv == n + 1 )
    {
        tipar();
        return;
    }
    for( int i = 1 ; i <= n ; i++ )
    {
        if( v[ i ] || d1[ i + niv ] || d2[ niv - i + 10 ] )
            continue;
        v[ i ] = 1;
        d1[ i + niv ] = 1;
        d2[ niv - i + 10 ] = 1;
        st[ niv ] = i;
        backtr( niv + 1 );
        v[ i ] = 0;
        d1[ i + niv ] = 0;
        d2[ niv - i + 10 ] = 0;
    }
}
int main()
{
    fin>>n;
    backtr( 1 );
    fout<<'\n'<<rsp;
}