#include <iostream>
#include <fstream>
using namespace std;

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

int n, ans;
int x[100], l[100], d1[100], d2[100];

void afisare () {
    for(int i = 1; i <= n; ++i)
        fout << x[i] << " ";
    fout << '\n';
}

void bk (int k) {
    for(int i = 1; i <= n; ++i) {
        if(l[i] == 0 && d1[i - k + n] == 0 && d2[k + i] == 0) {
            x[k] = i;
            l[i] = d1[i - k + n] = d2[k + i] = 1;
            if(k == n) {
                ans += 1;
                if(ans == 1) afisare();
            }
            else bk(k+1);
            l[i] = d1[i - k + n] = d2[k + i] = 0;
        }
    }
}

int main()
{
    fin >> n;

    bk(1);
    fout << ans;
    return 0;
}