#include <cstdio>

using namespace std;

int total,n;
int st[20],fol[20];

int valid(int k){
    for(int i = 1; i < k; i++){
        if(st[k] == st[i] ||
           st[k] + k == st[i] + i ||
           st[k] - k == st[i] - i){
            return 0;
           }
    }
    return 1;
}
void afisare(){
    if(total == 0){
        for(int i = 1; i <= n; i++){
            printf("%d ",st[i]);
        }
        printf("\n");
    }
    total++;
}
void back(int k){
    for(int i = 1; i <= n; i++){
        if(fol[i] == 0){
            fol[i] = 1;
            st[k] = i;

            if(valid(k)){
                if(k == n)
                    afisare();
                else
                    back(k + 1);
            }
            fol[i] = 0;
        }
    }
}
int main()
{
    freopen("damesah.in","r",stdin);
    freopen("damesah.out","w",stdout);
    scanf("%d",&n);
    back(1);
    printf("%d",total);
    return 0;
}