#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(int k){
    for(int i=1;i<k;++i){
        if(abs(st[k]-st[i])==k-i) return 0;
    }
    return 1;
}
void backt(int k){
    for(int i=1;i<=n;++i){
        st[k]=i;
        if(!viz[i]&&verifica(k)){
            viz[i]=1;
            st[k]=i;
            if(k==n){
                nr++;
                if(!ok){
                for(int j=1;j<=n;++j){
                    g<<st[j]<<" ";
                }
                ok=1;
                }
            }
            else backt(k+1);
            viz[i]=0;
        }
    }
}
int main()
{
    f>>n;
    backt(1);
    g<<'\n'<<nr;
}