#include <fstream>
#include <vector>
#include <string>

using namespace std;

ifstream cin("damesah.in");
ofstream cout("damesah.out");

bool test(int n, vector<int> &sol){
	bool ok = true;
	for(int i = 1; i < n; i++){
		for(int j = i + 1; j <= n; j++)
			if(abs(sol[i] - sol[j]) == j - i){
				ok = false; 
				break;
			}
	}
	return ok;
}
int s = 0;
void backtr(int &n, int current, vector<int> &sol, vector<bool> &used, bool &found){

	if(current == n+1){
		
			if(test(n, sol)){
         s += 1;
         if(!found){
				for(int i = 1; i <= n; i++){
					cout << sol[i] << ' ';
					}
				cout << '\n';
				found = true;	
      }
			}
		return;
	}
	else{

		for(int i = 1; i <= n; i++){
			
			if(used[i])
				continue;
			else{
				sol[current] = i;
				used[i] = true;
				backtr(n, current + 1, sol, used, found);
				used[i] = false;
			}
		}
	}

}

int main(){
	int n; cin >> n;
	bool found = false;
	vector<int> sol(n + 1);
	vector<bool> used(n + 1);
	backtr(n, 1, sol, used, found);
  cout << s << '\n';
}