#include <fstream>

using namespace std;

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

const int MAX = 13;

int n, x[MAX + 1], nrSol;
bool c[MAX + 1], dp[2 * MAX], ds[2 * MAX];

void bck(int k){
        if(k == n + 1) {
                if(!nrSol) {
                        for(int i = 1; i <= n; i++)
                                out << x[i] << ' ';
                        out << '\n';
                }
                nrSol++;
        }else{
                for(int i = 1; i <= n; i++) {
                        if(!c[i] && !dp[n - k + i] && !ds[k + i - 1]) {
                                x[k] = i;
                                c[i] = dp[n - k + i] = ds[k + i - 1] = 1;
                                bck(k + 1);
                                c[i] = dp[n - k + i] = ds[k + i - 1] = 0;
                        }
                }
        }
}

int main(){

        in >> n;
        bck(1);
        out << nrSol;

        return 0;
}