#include <cstdio>

int v[15], d1[25], d2[25], l[15], c[15], n, f;

using namespace std;

void dame( int p )
{
    if( p==n )
        f++;
    else
    {
        int i, j=p;

        for( i=0;i<n;i++ )
            if( !l[i] && !d1[i+j] && !d2[n-i+j-1] )
            {
                c[j]=l[i]=d1[i+j]=d2[n-i+j-1]=1;

                if( f==0 )
                    v[p]=i+1;

                dame(p+1);

                c[j]=l[i]=d1[i+j]=d2[n-i+j-1]=0;
            }
    }
}

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

    int i;

    scanf( "%d", &n );

    dame(0);

    for( i=0;i<n;i++ )
        printf( "%d ", v[i] );

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

    return 0;
}