#include <fstream>

using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, v[20], d1[40], d2[40], lin[20];
long long sol;

void bt ( int poz ){
    if ( poz > n ){
        if ( !sol )
        {
            for ( int i=1; i <= n; i++ )
                g<<v[i]<<" ";
            g<<"\n";
        }
        sol++;
        return;
    }
    int j = poz;
    for ( int i = 1; i <= n; i++ )
        if ( !lin[i] && !d1[n-i+j] && !d2[2*n-i-j+1] ){
            lin[i] = 1;
            d1[n-i+j] = 1;
            d2[2*n-i-j+1] = 1;
            v[poz] = i;
            bt(poz+1);
            lin[i] = 0;
            d1[n-i+j] = 0;
            d2[2*n-i-j+1] = 0;
        }
}

int main()
{
    f>>n;
    bt ( 1 );
    g<<sol;
    /*for ( int i = 1; i<= n; i++, g<<"\n" )
        for ( int j =1; j <= n; j++ )
            g<<n-i+j<<" ";
    g<<"\n";
    for ( int i = 1; i<= n; i++, g<<"\n" )
        for ( int j =1; j <= n; j++ )
            g<<2*n-i-j+1<<" ";
    */
    return 0;
}