#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using vi = vector<int>;
using pi = pair<int, int>;
 
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define f first
#define s second
 
void setIO(string name = "") {
	cin.tie(0)->sync_with_stdio(0);
	if (sz(name)) {
		freopen((name + ".in").c_str(), "r", stdin);
		freopen((name + ".out").c_str(), "w", stdout);
	}
}

int n, cnt=0;
vector<bool> used(n+1);
bool app1[57], app2[57], prima=true;
#define app1 (app1+27)
#define app2 (app2+27)

void back_tracking(int pos, vector<int>&p) {
    if(n==pos) {
        if(prima) {
            for(int i:p)
                cout << i+1 << ' ';
            cout << "\n";
            prima=false;
        }
        ++cnt;
        return;
    }
    for(int val=0; val<n; ++val) {
        if(used[val]) continue;
        if(app1[pos+val] || app2[pos-val]) continue;

        p[pos]=val;
        used[val]=true;
        app1[pos+p[pos]]=app2[pos-p[pos]]=true;

        back_tracking(pos+1, p);

        used[val]=false;
        app1[pos+p[pos]]=app2[pos-p[pos]]=false;
    }
}

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