#include<cstdio>
using namespace std ;

#define maxn 14

int N, nr ;

int sol[maxn] ;

int sel[maxn][maxn] ;

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

void marcheaza(int i, int j, int val)
{
    for(int x = 1; x <= N; ++x)
    {
        sel[x][j] += val ;

        if( ok( i + x ) == true && ok( j + x ) == true )
            sel[i + x][j + x] += val ;

        if( ok( i + x ) == true && ok( j - x ) == true )
            sel[i + x][j - x] += 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( sel[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 ;
}