#include <stdio.h>

#define MAX_N 13

FILE *fout;
int n, nrSol;
int sol[MAX_N], col[MAX_N], d1[2 * MAX_N - 1], d2[2 * MAX_N - 1];

void dame( int l ) {
    int c;

    if ( l == n ) {
        if ( nrSol == 0 ) {
            for ( l = 0; l < n; l++ )
                fprintf( fout, "%d ", sol[l] + 1 );
        }
        nrSol++;
    } else {
        for ( c = 0; c < n; c++ ) {
            if ( col[c] == 0 && d1[l + c] == 0 && d2[l - c + n] == 0 ) {
                col[c] = d1[l + c] = d2[l - c + n] = 1;
                sol[l] = c;
                dame( l + 1 );
                col[c] = d1[l + c] = d2[l - c + n] = 0;
            }
        }
    }
}

int main() {
    FILE *fin;

    fin = fopen( "damesah.in", "r" );
    fscanf( fin, "%d", &n );
    fclose( fin );


    fout = fopen( "damesah.out", "w" );
    nrSol = 0;
    dame( 0 );
    fprintf( fout, "\n%d", nrSol );
    fclose( fout );

    return 0;
}