#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const int NMAX = 13;

bool col[NMAX + 1];
bool diag1[2 * NMAX + 1];
bool diag2[2 * NMAX + 1];

int cnt;
int afisat;
int n;

vector <int> ans;

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

int bkt( int lin ) {
    if ( lin == n + 1 ) {
        cnt ++;
        if ( !afisat ) {
            for ( auto it : ans ) {
                fout << it << ' ';
            }
            afisat = 1;
        }
    }
    for ( int c = 1; c <= n; c ++ ) {
        int d1 = lin + c;
        int d2 = NMAX + lin - c;
        if ( !col[c] && !diag1[d1] && !diag2[d2] ) {
            col[c]    = 1;
            diag1[d1] = 1;
            diag2[d2] = 1;

            ans.push_back( c );
            bkt( lin + 1 );
            ans.pop_back();

            col[c]    = 0;
            diag1[d1] = 0;
            diag2[d2] = 0;
        }
    }
}
int main() {
    fin >> n;
    bkt( 1 );
    fout << '\n' << cnt;
    return 0;
}