#include <cstdio>
using namespace std;
int col[14],diagp[28],diags[28],v[14],n,s;
void back(int lin)
{
    int i;
    if(lin==n+1){
        if(s==0){
            for(i=1;i<=n;i++){
                printf("%d ",v[i]);
                             }
                }
        s++;return;
                }
    for(i=1;i<=n;i++){
        v[lin]=i;
        if((col[i]==0)&&(diagp[i+n-lin]==0)&&(diags[i+lin-1]==0)){
            col[i]=1;diagp[i+n-lin]=1;diags[i+lin-1]=1;
            back(lin+1);
            col[i]=0;diagp[i+n-lin]=0;diags[i+lin-1]=0;
                                           }
                     }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    back(1);
    printf("\n%d",s);
return 0;
}