#include <bits/stdc++.h>
#define MOD 1999999973
#define ull unsigned long long
#define FOR(i, a, b) for(i = a; i <= b; i++)

using namespace std;

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

int v[20];
int dp[30];
int ds[30];
int lin[20];
int n,ok = 0,c = 0;

bool eok(int k){
    if(dp[n + v[k] - k] == 1){
        return 0;
    }
    if(ds[v[k] + k -1] == 1){
        return 0;
    }
    if(lin[v[k]] == 1){
        return 0;
    }
    return 1;
}

void backtr(int k){
    int i;
    for(i = 1; i <= n; i++){
        v[k] = i;
        if(eok(k)){
            dp[n + i - k] = 1;
            ds[i + k -1] = 1;
            lin[i] = 1;
            if(k < n){
                backtr(k+1);
            }else{
                if(ok == 0){
                    ok = 1;
                    for(int j = 1; j <= n; j++){
                        fout<<v[j]<<" ";
                    }
                    fout<<'\n';
                }
                c++;
            }
            dp[n + i - k] = 0;
            ds[i + k -1] = 0;
            lin[i] = 0;
        }
    }
}

int main()
{
    fin>>n;
    backtr(1);
    fout<<c;
    return 0;
}