#include <cstdio>
using namespace std;
FILE * is = fopen("damesah.in", "r");
FILE * os = fopen("damesah.out", "w");

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

int main()
{
    fscanf(is, "%d", &n);
    SOLVE(1);
    fprintf(os, "\n%d", cnt);
    fclose(is);
    fclose(os);
    return 0;
}

void SOLVE(int k)
{
    if ( k > n )
    {
        ++cnt;
        if(cnt == 1)
            for(int j = 1; j <= n; ++j)
                fprintf(os, "%d ", x[j]);
        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;
    }
}