#include <bits/stdc++.h>

#define DIM 13

using namespace std;

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

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

int n;
int sol = 0;
int v[DIM+5];
int u[DIM+5];
int d1[2*DIM+5];
int d2[2*DIM+5];

void bkt(int pas){

    if(pas == n+1){

        sol++;

        if(sol == 1){
            for(int i=1;i<=n;i++){
                g<<v[i]<<" ";
            }g<<'\n';
        }

        return;
    }

    for(int i=1;i<=n;i++){
        if(!u[i] && !d1[i+pas] && !d2[n-i+pas]){

            v[pas] = i;

            u[i] ++;
            d1[i+pas] ++;
            d2[n-i+pas] ++;

            bkt(pas+1);

            u[i] --;
            d1[i+pas] --;
            d2[n-i+pas] --;
        }
    }
}

signed main()
{

    f>>n;

    bkt(1);

    g<<sol;

    return 0;
}