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

int n,nr;
int x[maxn],sol[maxn];
int C[maxn],Dp[maxn],Ds[maxn];

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(!C[i] && !Dp[i-k+1] && !Ds[i+k-1]){
         x[k]=i;
         C[i]++; Dp[i-k+1]++; Ds[i+k-1]++;
         back(k+1);
         C[i]--; Dp[i-k+1]--; Ds[i+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;
}