#include <stdio.h>
#define N 14
bool d_p[N * 2], d_s[N * 2], col[N];
int sol[N],solutii;

void backtracking(int n, int k)
{
    if( k == n)
    {
        if(!solutii)
        {
            for(int i = 0; i < n; ++i)
                printf("%d ",sol[i]);
        }
        ++solutii;
    }
    for(int i = 0; i < n; ++i)
    {
        if(!col[i] && !d_p[n - 1 + k - i] && !d_s[k + i])
        {
            sol[k] = i + 1;
            d_p[n - 1 + k - i] = d_s[k + i] = col[i] = true;
            backtracking(n,k+1);
            d_p[n - 1 + k - i] = d_s[k + i] = col[i] = false;
        }
    }
}

int main()
{
    int n;
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    backtracking(n,0);
    printf("\n%d",solutii);

}