#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define ft(n) for(int i=1; i<=n; i++)
#define sp ' '
string file = "damesah";
ifstream f(file + ".in");
ofstream g(file + ".out");

int n, ct = 0;
vector<int> v(20);

void write()
{
    ct++;
    if (ct == 1) {
        for (int i = 1; i <= n; i++)
            g << v[i] << sp;
        g << "\n";
    }
}

int chk(int ci) //current i
{
    for (int i = 1; i < ci; i++)
        if (v[ci] == v[i])
            return 0;
        else if (abs(v[ci] - v[i]) == abs(ci - i))
            return 0;
    return 1;
}

void bkt(int i)
{
    for (int j = 1; j <= n; j++)
    {
        v[i] = j;
        if (chk(i))
            if (i == n)
                write();
            else
                bkt(i + 1);
    }
}

int main() {
    f >> n;
    bkt(1);
    g << ct;
    return 0;
}