#include <iostream>
#include <cstdio>

using namespace std;

int sol[10],col[10],dp[10],ds[10],n,nrs,ok;

void afis()
{
    for ( int i = 1 ; i <= n ; ++i )
        printf ("%d " , sol[i]);
    ok=1;
}
void back(int k)
{
    if (k==n+1){
            if (ok==0)
                    afis();
            nrs++;
            }

    else
    for ( int i = 1 ; i <= n ; ++i )
        {
            if ((col[i]==0)&&(dp[k-i+n]==0)&&(ds[k+i]==0))
            {
                col[i]=dp[k-i+n]=ds[k+i]=1;
                sol[k]=i;
                back(k+1);
                col[i]=dp[k-i+n]=ds[k+i]=sol[k]=0;
            }
        }
}

int main()
{
    freopen ("damesah.in" , "r" , stdin );
    freopen ("damesah.out" , "w" , stdout );
    scanf ("%d" , &n );
    back(1);
    printf ("\n");
    printf ("%d" , nrs );
    return 0;
}