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

int n, x[15], cnt;
int di, dj;
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 )
    {
        ++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;
        di = k;
        dj = i;
        --di;
        --dj;
        while(di >= 1 && dj >= 1 )
        {
            if(x[di] == dj)
                break;
            --di;
            --dj;
        }
        if ( di >= 1 && dj >= 1 )
            continue;
        di = k;
        dj = i;
        --di;
        ++dj;
        while(di >= 1 && dj <= n )
        {
            if(x[di] == dj)
                break;
            --di;
            ++dj;
        }
        if ( di >= 1 && dj <= n )
            continue;
        ok[i] = true;
        x[k] = i;
        SOLVE(k+1);
        ok[i] = false;
    }
}