#include <bits/stdc++.h>

using namespace std;

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

int n;
int ans[15],dp[30],ds[30],col[15];
int sol = 0;

void afis()
{
    sol++;
    if (sol == 1)
    {
        for (int i = 1; i <= n; i++)
            out << ans[i] << ' ';
        out << '\n';
    }
}

void bkt(int pos)
{
    if (pos == n + 1)
        afis();
    else
    {
        for (int i = 1; i <= n; i++)
        {
            int diagp = 15 + pos - i,diags = i + pos;
            if (col[i] == 0 and dp[diagp] == 0 and ds[diags] == 0)
            {
                ans[pos] = i;
                col[i] = 1;
                dp[diagp] = 1;
                ds[diags] = 1;
                bkt(pos + 1);
                col[i] = 0;
                dp[diagp] = 0;
                ds[diags] = 0;
            }
        }
    }
}

int main()
{
    in >> n;
    bkt(1);
    out << sol;
    return 0;
}