#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
 
#define files(name) ifstream fin(name".in"); ofstream fout(name".out");
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define f first
#define s second

files("damesah")
 
bool Valid(int pos, const vector<int> &p) {
 	for (int i = 0; i < pos; ++i) {
    	if (p[i] == p[pos]) {
         	return false; 	
        }
        // de la st la dr
        if(pos-p[pos]==i-p[i])
            return false;
        // de la dr la st
        if(pos+p[pos]==i+p[i])
            return false;
    }
  	return true;
}
 
bool prima=true;
int cnt=0;
 
void Backtracking(int pos, vector<int> &p) {
    int n = p.size();	
    if (pos == n) {
        if(prima) {
            for(int i=0; i<n; ++i)
                fout << p[i] << ' ';
            fout << '\n';
            prima=false;
        }
        ++cnt;
        return;
    }
  
    for (int val = 1; val <= n; ++val) {
        p[pos] = val;
        if (Valid(pos, p))
            Backtracking(pos + 1, p); 
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;
    fin >> n;
  	vector<int> p(n);
	Backtracking(0, p);
    fout << cnt << "\n";
    return 0;
}