#include <stdio.h>
#define DIM 30


int N, C[DIM], DP[2 * DIM], DS[2 * DIM], cnt, L[DIM];

void print_table(){
    int i;

    for(i = 1; i <= N ; i++)
        printf("%d ", L[i]);

    printf("\n");

}

void back(int step){

    if(step==N+1){
        if(cnt==0)
            print_table();
        cnt++;
    }

    int i;

    for( i = 1 ; i <= N ; i++)
        if(!C[i] && !DP[step - i + DIM] && !DS[step + i]){
            C[i] = 1;
            DP[step - i + DIM] = 1;
            DS[step + i] = 1;
            L[step] = i;
            back(step+1);
            C[i] = 0;
            DP[step - i + DIM] = 0;
            DS[step + i] = 0;
        }
}


int main(){

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

    scanf("%d", &N);

    back(1);

    printf("%d\n", cnt);

    printf("\n");

    return 0;

}