#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 20
using namespace std;

int n,nr;
int x[maxn],sol[maxn];

int check(int k,int j)
{
    for(int i=1;i<k;i++)
     if(x[i]==j || abs(k-i)==abs(j-x[i])) return 0;
    return 1;
}

void back(int k)
{
    if(k>n){
        nr++; if(nr==1) memcpy(sol,x,sizeof(x));
        return;
    }
    for(int i=1;i<=n;i++)
     if(check(k,i)){
         x[k]=i;
         back(k+1);
     }
}

void print()
{
    for(int i=1;i<=n;i++) printf("%d ",sol[i]);
    printf("\n%d",nr);
}

int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);

    scanf("%d",&n);
    back(1);
    print();

    fclose(stdin);
    fclose(stdout);
    return 0;
}