# include <iostream>
# include <fstream>

using namespace std;

const int MAX_N = 13;
bool col[MAX_N], lin[MAX_N], dg1[2 * MAX_N], dg2[2 * MAX_N];

int n, k;
int sol[MAX_N];

void brute_force( int p ) {
    if ( p == n )
        k ++;
    else {
        const int y = p;
        for ( int x = 0; x < n; x ++ )
            if ( !lin[x] && !dg1[x + y] && !dg2[n - 1 - x + y] ) {
                col[y] = lin[x] = dg1[x + y] = dg2[n - 1 - x + y] = 1;

                if ( k == 0 )
                    sol[p] = x;

                brute_force( p + 1 );

                col[y] = lin[x] = dg1[x + y] = dg2[n - 1 - x + y] = 0;
            }
    }
}

int main() {
    ifstream fin( "damesah.in" );
    ofstream fout( "damesah.out" );

    fin >> n;

    brute_force( 0 );

    for ( int i = 0; i < n; i ++ )
        fout << sol[i] + 1 << ' ';
    fout << endl << k;

    fin.close();
    fout.close();

    return 0;
}