#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
using namespace std;
const int NMAX = 20;
int n,st[NMAX],vf[NMAX],ans;
int precalc[20] = {};
bool gasit = false;

ifstream fin("dame.in");
ofstream fout("dame.out");

bool check(int pas){
    for(int i = 1; i < pas; i++){
        if(pas-i == abs(st[pas] - st[i])){
            return false;
        }
    }
    return true;
}

void bkt(int pas){
    if(pas == n+1){
        ans++;
        if(ans == 1){
            for(int i = 1; i <= n; i++){
                cout << st[i] << " ";
            }
            cout << "\n";
        }
    }else{
        for(int i = 1; i <= n; i++){
            if(vf[i] == 0){
                vf[i] = 1;
                st[pas] = i;
                if(check(pas)){
                    bkt(pas+1);
                }
                vf[i] = 0;
            }
        }
    }
}

int main()
{
    fin >> n;
    bkt(1);
    fout << ans;
    return 0;
}