#include <fstream>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")

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

int col[14],diag1[25],diag2[25],rasp[14],poz[14],stg,cntsol,n;

void backtrack(int a){
    int i;
    if(a==n+1){
        cntsol++;
        if(stg==1){
            for(i=1;i<=n;i++) rasp[i]=poz[i];
            stg=0;
        }
    }
    for(i=1;i<=n;i++){
        if(col[i]==0 && diag1[n+a-i]==0 && diag2[a+i]==0){
            col[i]=1;
            diag1[n+a-i]=1;diag2[a+i]=1;
            poz[a]=i;
            backtrack(a+1);
            col[i]=0;
            diag1[n+a-i]=0;diag2[a+i]=0;
        }
    }
}

int main()
{
    int poz=1,i;stg=1;
    cin>>n;
    backtrack(1);
    for(i=1;i<=n;i++) cout<<rasp[i]<<" ";
    cout<<"\n"<<cntsol;
    return 0;
}