#include <cstdio>
#include <cstdlib>
using namespace std;

int n, st[20], p, ok, nr, ap[20], ap2[100], ap3[100];

void permut (int k)
{
        if (k==n+1){
            nr++;
            if (nr==1){
                for (int i=1; i<=n; i++)
                    printf("%d ", st[i]);
                printf("\n");
            }
        }
        else{
            for (int x=1; x<=n; x++){
                if (ap[x]==0 && ap2[k+x]==0 && ap3[x-k+n-1]==0){
                    st[k]=x;
                    ap[x]=ap2[k+x]=ap3[x-k+n-1]=1;
                    permut(k+1);
                    ap[x]=ap2[k+x]=ap3[x-k+n-1]=0;
            }
        }
    }
}

int main (){
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d", &n);
    permut(1);
    printf("%d", nr);
    return 0;
}