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

#define Nmax 15

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

bitset < 2*Nmax > line, column, mainDiag, secDiag;
int st[Nmax], sol[Nmax], N, nrs;

void bkt ( int niv ){
    if ( niv > N ){
        if ( sol[1] == 0 )
            for ( int i = 1; i <= N; ++i )
                sol[i] = st[i];
        nrs++;
        return;
    }

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

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

int main(){

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

    bkt ( 1 );

    for ( int i = 1; i <= N; ++i )
        fprintf ( g, "%d ", sol[i] );

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

    return 0;
}