#include <fstream>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n;
int vfcoloana[19];
int vfdiagp[40];
int vfdiags[40];
int ans[19];
int cnt;
void bkt(int pas){
    if(pas==n+1){
        if(cnt==0){
            for(int i=1;i<=n;i++){
                fout<<ans[i]<<" ";
            }
            fout<<endl;
        }
        cnt++;
        return ;
    }
    for(int i=1;i<=n;i++){
        bool ok=1;
        if(vfcoloana[i]==0&&vfdiagp[pas-i+n]==0&&vfdiags[pas+i]==0){
            ans[pas]=i;
            vfcoloana[i]=1;
            vfdiagp[pas-i+n]=1;
            vfdiags[pas+i]=1;
            bkt(pas+1);
            vfcoloana[i]=0;
            vfdiagp[pas-i+n]=0;
            vfdiags[pas+i]=0;
        }
    }
}
int main(){
    fin>>n;
    bkt(1);
    fout<<cnt;
    return 0;
}