#include <fstream>
using namespace std;

void gen(int r, int n, int sol[], int &nr_sol, ostream &out,
        bool col[], bool mellek[], bool fo[])
{
    if (r > n) {
        ++nr_sol;
        if (nr_sol == 1) {
            for (int i = 1; i <= n; i++)
                out << sol[i] << " ";
            out << "\n";
        }
    } else {
        for (int c = 1; c <= n; c++) {
            if (!col[c] && !mellek[r+c] && !fo[r-c+n]) {
                sol[r] = c;

                col[c] = true;
                mellek[r+c] = true;
                fo[r-c+n] = true;

                gen(r+1, n, sol, nr_sol, out, col, mellek, fo);

                col[c] = false;
                mellek[r+c] = false;
                fo[r-c+n] = false;
            }
        }
    }
}

int main()
{
    ifstream fin("damesah.in");
    ofstream fout("damesah.out");
    //ifstream fin("input.txt");
    //ofstream fout("output.txt");

    int n;
    fin >> n;

    int nr_sol = 0;
    int sol[20];

    bool col[20] = {}; // col[i] - foglalt-e az i. oszlop
    bool mellek[50] = {}; // mellek[x] - foglalt-e az a mellékátlóval
                          // párh. vonal, ahol az összeg x
    bool fo[50] = {}; // fo[x] - foglalt-e az a főátlóval
                      // párh. vonal, ahol i-j+n == x

    gen(1, n, sol, nr_sol, fout, col, mellek, fo);

    fout << nr_sol << "\n";

    return 0;
}