#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()
{
    
}

void bkt(int i)
{
    for (int j = 1; j <= n; j++)
    {
        v[i] = j;
        //check
        bool chk = 1;
        int ci = i;
        for (int i = 1; i < ci && chk; i++)
            if (v[ci] == v[i])
                chk = 0;
            else if (abs(v[ci] - v[i]) == abs(ci - i))
                chk = 0;
        if (chk)
            if (i == n) {
                //write
                ct++;
                if (ct == 1) {
                    for (int i = 1; i <= n; i++)
                        g << v[i] << sp;
                    g << "\n";
                }
            }
            else
                bkt(i + 1);
    }
}

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