#include<fstream>
#include<cmath>
using namespace std;
ifstream f ("damesah.in");
ofstream g ("damesah.out");
int i,st[20],viz[20],n,nr,ok;
bool verifica(){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(abs(st[i]-st[j])==j-i) return 0;
        }
    }
    return 1;
}
void backt(int k){
    for(int i=1;i<=n;i++){
        if(!viz[i]){
            viz[i]=1;
            st[k]=i;
            if(k==n){
                if(verifica()){
                    nr++;
                    for(int j=1;j<=n&&!ok;j++){
                        g<<st[j]<<" ";
                    }
                    ok=1;
                }
            }
            else backt(k+1);
            viz[i]=0;
        }
    }
}
int main()
{
    f>>n;
    backt(1);
    g<<'\n'<<nr;
}