#include <bits/stdc++.h>
using namespace std;
int n,st[15];
int ap_col[15],ap_diag_p[31],ap_diag_s[32];
int nr_sol;
void Back(int k){
    if(k==n+1){
        ++nr_sol;
        if(nr_sol==1){
            for(int i=1;i<=n;++i)
                printf("%d ",st[i]);
            printf("\n");
        }
    }
    for(int i=1;i<=n;++i)
        if(!ap_col[i]&&!ap_diag_p[i-k+n]&&!ap_diag_s[i+k-1]){
            st[k]=i;
            ap_col[i]=ap_diag_p[i-k+n]=ap_diag_s[i+k-1]=1;
            Back(k+1);
            ap_col[i]=ap_diag_p[i-k+n]=ap_diag_s[i+k-1]=0;
        }
}
int main(){
    freopen("damesah.in	", "r", stdin);
    freopen("damesah.out", "w", stdout);
    scanf("%d",&n);
    Back(1);
    printf("%d\n",nr_sol);
    return 0;
}