// Nqueen.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include "iostream.h"
#include "math.h"
class Queen {
friend int nQueen(int);
private:
bool Place(int k);
void Backtrack(int t);
int n,*x;
long sun;
};
bool Queen::Place(int k) {
for(int j = 1;j<k;j++)
if((abs(k - j) == abs(x[k] - x[j])) || (x[j] == x[k])) return false;
return true;
}
void Queen::Backtrack(int t) {
if(t > n) sun++;
else for(int i = 1;i<=n;i++) {
x[t] = i;
if(Place(t)) Backtrack(t + 1);
}
}
int nQueen(int n) {
Queen X;
X.n = n;
X.sun = 0;
int *p = new int[n+1];
for(int i = 0;i <= n;i++)
p[i] = 0;
X.x = p;
X.Backtrack(1);
delete [] p;
return X.sun;
// ruturn X.x;
}
void main() {
int n;
cin>>n;
cout<<nQueen(n)<<endl;
}
