#include<fstream>

using namespace std;

ifstream fin( "damesah.in" );
ofstream fout( "damesah.out" );

const int nmax = 13;
int n, sol, v[ nmax ], col[ nmax ], d1[ 2 * nmax + 1 ], d2[ 2 * nmax + 1 ];

void bkt( int x ) {
    if ( x == n ) {
        if ( sol == 0 ) {
            for( int i = 0; i < n; ++ i ) {
                fout<<v[ i ] + 1<<' ';
            }
            fout<<'\n';
        }
        ++ sol;
        return ;
    }
    for( int i = 0; i < n; ++ i ) {
        if ( col[ i ] == 0 && d2[ i + x ] == 0 && d1[ x - i + n - 1 ] == 0 ) {
            v[ x ] = i;
            col[ i ] = d2[ i + x ] = d1[ x - i + n - 1 ] = 1;
            bkt( x + 1 );
            col[ i ] = d2[ i + x ] = d1[ x - i + n - 1 ] = 0;
        }
    }
}
int main() {
    fin>>n;
    sol = 0;
    bkt( 0 );
    fout<<sol<<'\n';
    fin.close();
    fout.close();
    return 0;
}