#include <bits/stdc++.h>

using namespace std;

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

int n, l[50], c[50], d1[50], d2[50], k;

void bk(int p) {
    int i;
    if(p==n+1) {
        if(k==0) {
            for(i=1; i<=n; i++)
                if(l[i])
                fout<<l[i]<<" ";
            fout<<'\n';
            k++;
        }
        else k++;
    }
    for(i=1; i<=n; i++)
        if(c[i] == 0 && d1[i+p] == 0 && d2[i-p+n+1] == 0) {
                l[p]=i;
                c[i] = 1;
                d1[i+p] = 1;
                d2[i-p+n+1] = 1;
                bk(p+1);
                c[i] = 0;
                d1[i+p] = 0;
                d2[i-p+n+1] = 0;
            }
}
int main() {
    fin>>n;
    bk(1);
    fout<<k;
    return 0;
}