#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("damesah.in");
ofstream fout ("damesah.out");

int sol[16], col[16], dp[33], ds[33], n, sum=0;
bool esol=0;

void bkt(int k){
    if (k==n){
        if (esol==0){
            for (int i=0; i<n; ++i)
                fout<<sol[i]+1<<' ';
                esol=1;
        } 
    ++sum;
    return;
    }
    for (int i=0; i<n; ++i)
        if (col[i]==0 && dp[k-i+15]==0 && ds[i+k]==0){ //if(OK) si ii fara linie ca oricum se reseteaza cand revine inapoi in bucla //ds[i-k+k*2+15]==0
                sol[k]=i;

                col[i]=1;
                dp[k-i+15]=1;
                ds[i+k]=1;

                bkt(k+1);

                col[i]=0;
                dp[k-i+15]=0;
                ds[i+k]=0;
            } 
}

int main(){
    fin>>n;
    bkt(0);
    fout<<'\n'<<sum;
    fin.close(), fout.close();
    return 0;
}