#include <fstream>
using namespace std;

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

int n,cnt,v[20],col[20],d1[20],d2[20];

void sheah(int pas){
    if(pas>n){
        cnt++;
        if(cnt==1){
            for(int i=1;i<=n;i++)
                fout<<v[i]<<" ";
            fout<<"\n";
        }

        return;
    }

    for(int i=1;i<=n;i++){
        if(col[i]==0 && d1[pas+i]==0 && d2[pas-i]==0){
            col[i]=1;
            d1[pas+i]=1;
            d2[pas-i]=1;
            v[pas]=i;
            sheah(pas+1);
            col[i]=0;
            d1[pas+i]=0;
            d2[pas-i]=0;
        }
    }
}

int main(){
    fin>>n;
    sheah(1);
    fout<<cnt;

    return 0;
}