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

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