#include <bits/stdc++.h>
using namespace std;

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

const int NMAX = 15;

bitset <NMAX> fr;
bool gasit = false;
int v[NMAX];
int cnt;
int n;

void afis() {
    for(int i = 1; i <= n; i++)
        out << v[i] << " ";
    out << '\n';
    gasit = true;
}

inline bool ok(int poz) {
    for(int i = 1; i < poz; i++)
        if(v[poz] == v[i] || abs(v[i] - v[poz]) == abs(i - poz))
            return false;
    return true;
}

void bkt(int poz) {
    for(int i = 1; i <= n; i++) {
        v[poz] = i;
        if(!fr[i] && ok(poz)) {
            if(poz == n) {
                if(!gasit)
                    afis();
                cnt++;
            } else {
                fr[i] = true;
                bkt(poz + 1);
                fr[i] = false;
            }
        }
    }
}

int main()
{
    in >> n;
    bkt(1);
    out << cnt;
    return 0;
}