#include <fstream>
#define NMAX 60

using namespace std;

ifstream f ("damesah.in");
ofstream g ("damesah.out");

int v[ NMAX ], ans2, n, diagsus[ NMAX ], diagjos[ NMAX ], uz[ NMAX ], diagsec[ NMAX ], ok;

int check( int a, int b )
{
    if( a - b >= 0 )
    {
        if ( diagjos[ a - b ] == 0 )
            return 1;
    }

    if ( a - b < 0 )
    {
        if ( diagsus[ b - a ] == 0 )
            return 1;
    }

    return 0;
}

int check2( int a, int b )
{
    if ( diagsec[ a + b ] == 0 )
        return 1;

    return 0;
}

void afisare()
{
    for ( int i = 1; i <= n; i ++ )
        g << v[ i ] << " ";

    g << "\n";
}

void bk( int pas )
{
    if ( pas == n + 1 )
    {
        ans2++;

        if( !ok )
        {
            afisare();
            ok = 1;
        }

        return;
    }

    for ( int i = 1; i <= n; i ++ )
    {
        if( !uz[ i ] && check ( pas, i ) && check2( pas, i ) )
        {
            uz[ i ] = 1;
            diagsec[ pas + i ] = 1;

            if( pas >= i )
                diagjos [ pas - i ] = 1;
            else
                diagsus[ i - pas ] = 1;

            v[ pas ] = i;
            bk ( pas + 1 );

            uz[ i ] = 0;

            if ( pas >= i )
                diagjos[ pas - i ] = 0;
            else
                diagsus[ i - pas ] = 0;

            diagsec[ pas + i ] = 0;
        }
    }
}

int main()
{
    f >> n;
    bk( 1 );

    g << ans2;
}