#include <fstream>
#include <bitset>
using namespace std;
ofstream fout("damesah.out");
ifstream fin("damesah.in");

const int NMAX = 14;

int N, nr, first = 1;
int sol[NMAX];
bitset<NMAX * 2> col, diag_p, diag_s;

void bkt(int k)
{
    if(k > N) {
        nr++;
        if(first) {
            for(int i=1; i<=N; i++) fout << sol[i] << ' ';
            fout << '\n';
            first = false;
        }
        return;
    }

    for(int i=1; i<=N; i++) {
        sol[k] = i;

        if(!col[i] && !diag_p[i-k+8] && !diag_s[i+k-1]) {
            col[i] = true;
            diag_p[i-k+8] = true;
            diag_s[i+k-1] = true;

            bkt(k+1);

            col[i] = false;
            diag_p[i-k+8] = false;
            diag_s[i+k-1] = false;
        }
    }
}

int main()
{
    fin >> N;
    bkt(1);
    fout << nr << '\n';
    return 0;
}