#include <bits/stdc++.h>

using namespace std;


//int arr[201];
//#define arr (arr+100)

// bool arr[mxN]

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)
                cout << p[i] << ' ';
            cout << '\n';
            prima=false;
        }
        ++cnt;
        return;
    }
  
    for (int val = 1; val <= n; ++val) {
        // vrem sa punem val pe pozitia pos in permutare
        p[pos] = val;
        if (Valid(pos, p))
            Backtracking(pos + 1, p); 
    }
}

int main() {
    int n;
    cin >> n;
  	vector<int> p(n);
	Backtracking(0, p);
    cout << cnt << "\n";
    return 0;
}