#include <fstream>

using namespace std;

const int Nmax=15;

int v[15],sol=0,n;

ofstream fout("damesah.out");

bool isValid(int k) {
    for (int i=1; i<k; ++i) {
        if (v[i]==v[k] || k-i==abs(v[k]-v[i])) {
            return 0;
        }
    }
    return 1;
}

void bkt(int k) {
    if (k==n+1) {
        sol++;
        if (sol==1) {
            for (int i=1; i<=n; ++i) {
                fout<<v[i]<<' ';
            }
            fout<<endl;
        }
    }
    else {
        for (int i=1; i<=n; ++i) {
            v[k]=i;
            if (isValid(k)) {
                bkt(k+1);
            }
        }
    }
}

int main()
{
    ifstream fin("damesah.in");
    fin>>n;
    bkt(1);
    fout<<sol;
    fin.close();
    fout.close();
    return 0;
}