#include <iostream>
#include <fstream>
using namespace std;
const int Maxx=1e1+5;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
bool dg1[2*Maxx+1];
#define dg1 (dg1+100)
bool dg2[2*Maxx+1];
//#define dg2 (dg2+100)
bool line[Maxx];
int sol[Maxx];
int n,ans;
bool ft=false;
void bk(int k){
    int i;
    if (k==n+1){
        if (!ft){
            ft=true;
            for (i=1;i<=n;++i){
                fout<<sol[i]<<" ";
            }
        }
        ++ans;
        return;
    }
    for (i=1;i<=n;++i){
        sol[k]=i;
        if (!line[i] && !dg1[i-k] && !dg2[i+k]){
            line[i]=dg1[i-k]=dg2[i+k]=1;
            bk(k+1);
            line[i]=dg1[i-k]=dg2[i+k]=0;
        }
    }
}
int main() {
    fin>>n;
    bk(1);
    fout<<"\n"<<ans;
    return 0;
}