#include <fstream>

using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");

#define DIM 15

void Back(int);
bool Valid(int,int);
void Write();

int n;
int a[DIM][DIM];
int v[DIM];
int ans;

int main()
{
    fin >> n;

    Back(1);

    for ( int i = n; v[i]; --i )
        fout << v[i] << ' ';

    fout << endl;

    fout << ans;

    fin.close();
    fout.close();
    return 0;
}

void Write()
{
    for ( int i = 1; i <= n; ++i )
        for ( int j = 1; j <= n; ++j )
            if ( a[i][j] )
                v[i] = j;
}

bool Valid(int i, int j)
{
    for ( int k = 1; k < j; ++k )
        if ( a[i][k] )
            return false;
    for ( int x = i, y = j; x > 0 && j > 0; x--, y-- )
        if ( a[x][y] )
            return false;
    for ( int x = i, y = j; x <= n && y > 0; x++, y-- )
        if ( a[x][y] )
            return false;
    return true;
}

void Back(int i)
{
    if ( i > n )
    {
        if ( ans == 0 )
            Write();
        ans++;
    }
    for ( int j = 1; j <= n; ++j )
    {
        if ( Valid(j,i) )
            {
                a[j][i] = 1;
                Back( i + 1 );
                a[j][i] = 0;
            }
    }
}