#include <fstream>
#include <vector>
using namespace std;

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

int n, answ;
vector<int> x;
vector<bool> l, dd, du, dl, dr;

void SOLVE(int k);
void WRITE(int k);

int main()
{
    is >> n;
    x.resize(n + 1);
    l.resize(n + 1);
    dd.resize(n + 1);
    du.resize(n + 1);
    dr.resize(n + 1);
    dl.resize(n + 1);
    //WRITE(1);
    SOLVE(1);
    os << answ;
    is.close();
    os.close();
    return 0;
}

void SOLVE(int k)
{
    if ( k > n )
    {
        ++answ;
        if ( answ == 1 )
        {
            for ( int i = 1; i <= n; ++i )
                os << x[i] << " ";
            os << "\n";
        }
        return;
    }
    for ( int i = 1; i <= n; ++i )
    {
        if ( l[i] )
            continue;
        if ( i < k )
        {
            if ( dr[k - i] )
                continue;
        }
        else
            if ( dl[i - k] )
                continue;
        if ( n - k >= i )
        {
            if ( du[k + i] )
                continue;
        }
        else
            if ( dd[k + i] )
                continue;
        l[i] = true;
        if ( i < k )
            dr[k - i] = true;
        else
            dl[i - k] = true;
        if ( n - k >= i )
            du[k + i] = true;
        else
            dd[k + i] = true;
        x[k] = i;
        SOLVE(k + 1);
        l[i] = false;
        if ( i < k )
            dr[k - i] = false;
        else
            dl[i - k] = false;
        if ( n - k >= i )
            du[k + i] = false;
        else
            dd[k + i] = false;
    }
}