#include <fstream>
using namespace std;

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

bool coloana[15];
bool diagonala1[30];
bool diagonala2[30];
int nr_sol = 0;
int regine[15];

void afis(int n) {
    for (int i = 1; i <= n; ++i) {
        fout << regine[i] << ' ';
    }
    fout << '\n';
}

void back(int k, int n) {
    if (k == n + 1) {
        nr_sol++;
        if (nr_sol == 1) {
            afis(n);
        }
    } else {
        for (int i = 1; i <= n; ++i) {
            if (coloana[i] == 0 && diagonala1[n + k - i] == 0
                && diagonala2[k + i] == 0) {
                coloana[i] = 1;
                diagonala1[n + k - i] = 1;
                diagonala2[k + i] = 1;
                regine[k] = i;

                back(k + 1, n);

                coloana[i] = 0;
                diagonala1[n + k - i] = 0;
                diagonala2[k + i] = 0;
            }
        }
    }
}

int main() {
    int n;
    fin >> n;

    back(1, n);

    fout << nr_sol;
    return 0;
}