#include <stdio.h>

#define N_MAX 13

FILE * fout;
int N;

typedef char bool;

bool lin[ N_MAX + 1 ], col[ N_MAX + 1 ], d1[ 2 * N_MAX - 1 ], d2[ 2 * N_MAX - 1 ];
int buffer[ N_MAX + 1 ], found;

void bkt( int l ) {
    if( l == N + 1 ) {
        if( found == 0 ) {
            int i;
            for( i = 1; i <= N; i ++ ) {
                fprintf( fout, "%d ", buffer[ i ] );
            }
            fprintf( fout, "\n" );
        }
        found ++;
    } else {
        int i;
        for( i = 1; i <= N; i ++ ) {
            if( ! ( lin[ l ] || col[ i ] || d1[ i - l + N ] || d2[ i + l - 1 ] ) ) {
                buffer[ l ] = i;
                lin[ l ] = 1;
                col[ i ] = 1;
                d1[ i - l + N ] = 1;
                d2[ i + l - 1 ] = 1;
                bkt( l + 1 );
                d2[ i + l - 1 ] = 0;
                d1[ i - l + N ] = 0;
                col[ i ] = 0;
                lin[ l ] = 0;
            }
        }
    }
}

int main( ) {
    FILE * fin;
    fin = fopen( "damesah.in", "r" );
    fout = fopen( "damesah.out", "w" );

    fscanf( fin, "%d", &N );

    bkt( 1 );
    fprintf( fout, "%d\n", found );

    fclose( fin );
    fclose( fout );
}