#include <bits/stdc++.h>
using namespace std;
const int N = 50;
bool row[N], line[N], d[N], rd[N];
int ans[N];
int n, cnt;

void dfs(int l){
    if(l == n + 1)
        {
            if(cnt < 3){
            for(int i = 1;i <= n;i++)cout << ans[i] << " ";
                cout << endl;
        }
            cnt++;
            return;
        }


    for(int i = 1;i <= n;i++){
        if(row[i] || (l < i && d[i - l + n]) || (l >= i) && d[l - i] || rd[i + l])continue;
        if(l < i)d[i - l + n] = true;
        else d[l - i] = true;
        row[i] = true;
        rd[i + l] = true;
        ans[l] = i;
        dfs(l + 1);
        row[i] = false;
        rd[i + l] = false;
        if(l < i)d[i - l + n] = false;
        else d[l - i] = false;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    dfs(1);
    cout << cnt;
    return 0;
}