#include <fstream>
#define f in
#define g out

using namespace std;
ifstream in ( "damesah.in" );
ofstream out( "damesah.out" );
int n, sol, ok;
int v[200], d1[200], d2[200], fr[200];

void back ( int lin ){
    if ( lin > n  ){
        if ( !sol )
            for ( int i=1; i <= n; i++ )
                g<<v[i]<<" ";
        sol++;
        return;
    }
    for ( int col = 1; col <= n; col++ )
        if ( !fr[col] && !d1[n+col-lin] && !d2[col+lin] ){
            d1[n+col-lin] = 1; d2[col+lin] = 1; fr[col] = 1;
            v[lin] = col;
            back ( lin+1 );
            d1[n+col-lin] = 0; d2[col+lin] = 0; fr[col] = 0;
        }
}


int main() {
    f>>n;
    back ( 1 );
    g<<"\n"<<sol;
    return 0;
}