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

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

int n;
bool lin[20],col[20],dig1[40],dig2[40];
int v[20];
int ok=1;
int ctr;

int valid (int ln, int cl) {
    if (lin[ln]==1 || col[cl]==1 || dig1[ln-cl+n]==1 || dig2[ln+cl-1]==1) {
        return 0;
    }
    else {
        v[ln]=cl;
        lin[ln]=1;
        col[cl]=1;
        dig1[ln-cl+n]=1;
        dig2[ln+cl-1]=1;
        return 1;
    }
}

void afisare() {
    ok = 0;
    for (int o=1;o<=n;o++) {
        g << v[o] << " ";
    }
}

void bkt (int k) {
    for (int i=1;i<=n;i++) {
        if (valid(k,i)==1) {
            if (k==n) {
                if (ok==1) {
                    afisare();
                }
                ctr++;
            }
            else {
                bkt(k+1);
            }
            v[k]=0;
            lin[k]=0;
            col[i]=0;
            dig1[k-i+n]=0;
            dig2[k+i-1]=0;
        }
    }
}

int main()
{
    f >> n;
    bkt(1);
    g << '\n' << ctr;
    return 0;
}