#include <fstream>
using namespace std;
ifstream is ("damesah.in");
ofstream os ("damesah.out");

int n, x[15], cnt;
void SOLVE(int k);
bool Verif();
bool ok[15];

int main()
{
    is >> n;
    SOLVE(1);
    os << cnt;
    is.close();
    os.close();
    return 0;
}

void SOLVE(int k)
{
    if ( k > n )
    {
        if(Verif())
        {
            ++cnt;
            if(cnt == 1)
            {
                for(int j = 1; j <= n; ++j)
                    os << x[j] << ' ';
                os << '\n';
            }
        }
        return;
    }
    for ( int i = 1; i <= n; ++i)
    {
        if(ok[i])
            continue;
        if ( k != 1 && i > 1 && i < n )
        if ( x[k - 1] == i - 1 || x[k - 1] == i + 1 )
            continue;
        ok[i] = true;
        x[k] = i;
        SOLVE(k+1);
        ok[i] = false;
    }
}

bool Verif()
{
    int di, dj;
    for(int i = 1; i <= n; ++i)
    {
        di = i;
        dj = x[i];
        ++di;
        --dj;
        while(di <= n && dj >= 1 )
        {
            if(x[di] == dj)
                return false;
            ++di;
            --dj;
        }
        di = i;
        dj = x[i];
        ++di;
        ++dj;
        while(di <= n && dj <= n)
        {
            if(x[di] == dj)
                return false;
            ++di;
            ++dj;
        }
    }
    return true;
}