#include<cstdio>
using namespace std ;

#define maxn 14

int N, nr ;

int sol[maxn] ;

int sel_p[3 * maxn] ;
int sel_s[3 * maxn] ;
int selc[maxn] ;

bool ok(int L)
{
    return ( 0 < L && L <= N ) ;
}

void marcheaza(int i, int j, int val)
{
    selc[j] += val ;

    sel_p[ i - j + maxn ] += val ;

    sel_s[i + j] += val ;
}

void back(int level)
{
    if( level == N + 1 )
    {
        ++nr ;

        if( nr == 1 )
            for(int i = 1; i <= N; ++i )
                printf("%d ", sol[i]);

        return ;
    }
    for(int j = 1; j <= N; ++j )
    {
        if( selc[j] == 0 && sel_p[level - j + maxn] == 0 && sel_s[level + j] == 0 )
        {
            sol[level] = j ;
            marcheaza( level, j, 1 ) ;

            back(level + 1) ;

            sol[level] = 0 ;
            marcheaza( level, j, -1 ) ;
        }
    }
}

int main()
{
    freopen("damesah.in", "r", stdin);
    freopen("damesah.out", "w", stdout);

    scanf("%d", &N);

    back(1) ;

    printf("\n%d", nr);

    return 0 ;
}