#include <fstream>
using namespace std;

ifstream fin("damesah.in");
ofstream fout("damesah.out");
int c[100],d1[100],d2[100],j,n,ans,v[100];


bool valid(int k)
{
    if( c[ v[ k ] ]!=0 )
        return false;
    if( d1 [ k + v[ k ] ] != 0 )
        return false;
    if( d2 [ 16 + k - v[ k ] ] != 0 )
        return false;
    return true;
}

void backtracking(int k)
{
    int i;
    for(i=1 ; i<=n ; ++i)
    {
        v[k]=i;
        if( valid(k) )
        {
            if( k == n )
            {
                if( ans < 1 )
                {
                    for(int p=1 ; p<=n ; ++p)
                        fout<<v[p]<<' ';
                    fout<<'\n';
                }
                ++ans;
            }
            else
            {
                c[ i ] = k;
                d1[ k + i ] = k;
                d2[16 + k - i] = k;
                backtracking( k + 1 );
                c[ i ] = 0;
                d1[ k + i ] = 0;
                d2[16 + k - i ] = 0;
            }
        }


    }

}

int main()
{
    fin>>n;
    backtracking(1);
    fout<<ans;

return 0;
}