#include <iostream>
#include <fstream>
#define MAX 16
#define md col-lin+n-1
#define sd lin+col

using namespace std;

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

int n;
int queen[MAX];
bool cl[MAX];
bool maind[MAX];
bool secd[MAX];
int ans;

void bkt(int lin) {
    if(lin == n+1) {
        if(ans == 0) {
            for(int col = 1; col <= n; col++)
                out << queen[col] << " ";
            out << '\n';
        }
        ans++;
    } else {
        for(int col = 1; col <= n; col++) {
            if(!cl[col] && !maind[md] && !secd[sd]) {
                queen[lin] = col;
                cl[col] = true;
                maind[md] = true;
                secd[sd] = true;
                bkt(lin+1);
                cl[col] = false;
                maind[md] = false;
                secd[sd] = false;
            }
        }
    }
}

int main() {

    in >> n;
    bkt(1);
    out << ans << '\n';

    return 0;
}