#include <cstdio>
#include <bitset>
using namespace std;

#define Nmax 15

FILE *f = fopen ( "damesah.in", "r" );
FILE *g = fopen ( "damesah.out", "w" );

bitset < Nmax<<1 > column, mainDiag, secDiag;
int st[Nmax], N, nrs;
bool ans = 0;

void bkt ( int niv ){
    if ( niv > N ){
        if ( !ans ){
            for ( int i = 1; i <= N; ++i )
                fprintf ( g, "%d ", st[i] );
            ans = 1;
        }
        nrs++;
        return;
    }

    for ( int i = 1; i <= N; ++i ){
        if ( !column[i] && !mainDiag[i-niv+N] && !secDiag[niv+i] ){

            st[niv] = i;
            column[i] = mainDiag[i-niv+N] = secDiag[niv+i] = 1;
            bkt ( niv + 1 );
            column[i] = mainDiag[i-niv+N] = secDiag[niv+i] = 0;
        }
    }
}

int main(){

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

    bkt ( 1 );

    fprintf ( g, "\n%d", nrs );

    return 0;
}