#include <fstream>
using namespace std;

int n, st[20], fv[20], d1[50], d2[50], ver=0;

ifstream f ("damesah.in");
ofstream g ("damesah.out");


void bk (int nivel)
{

    if (nivel==n+1)
    {
        if (ver==0)
        {
            for (int i = 1; i<=n; i++)
            {
                g<<st[i]<<" ";
            }
        }

        ver++;

        return;
    }

    for (int i = 1 ; i <= n ; i++)
    {
        if ( fv[i]==0 && d1[nivel-i+10] == 0 && d2 [nivel - ( n-i ) + 10 ]  == 0 )
        {
            fv[i]=1;
            d1[nivel-i+10]=1;
            d2[nivel - ( n - i ) + 10 ] = 1;
            st[nivel]=i;
            bk ( nivel + 1 );
            fv[i]=0;
            d1[nivel-i+10]=0;
            d2[nivel - ( n - i ) + 10 ] = 0;
        }
    }

}


int main ()
{
    f>>n;

    bk(1);

    g<<'\n'<<ver;

    return 0;
}