#include <bits/stdc++.h>
using namespace std;

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

int n, x[15], l[15], d1[15], d2[15], sol;

void bkt(int k)
{
    if(k-1 == n)
    {
        sol++;
        if(sol == 1)
        {
            for(int i = 1; i <= n; i++) out << x[i] << ' ';
            out << '\n';
        }
    }
    else
    {
        for(int i = 1; i <= n; i++)
            if(!l[i] && !d1[i-k+n] && !d2[i+k])
            {
                l[i] = d1[i-k+n] = d2[i+k] = 1;
                x[k] = i;

                bkt(k+1);

                l[i] = d1[i-k+n] = d2[i+k] = 0;
            }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    in.tie(0);

    in >> n;

    bkt(1);

    out << sol;

    return 0;
}