#include <bits/stdc++.h>
///N=13
using namespace std;
///
int n, i, j, k;
long long cnt;
int lst[20], sol[20], diagL[40], diagR[40], col[20];
///
void read();
void solve();
void write();
void bkt(int line);
int main()
{
    read();
    solve();
    write();
    return 0;
}
void read(){
    freopen("damesah.in", "r", stdin);
    scanf("%d", &n);
    fclose(stdin);
}
void solve(){
    bkt(1);
}
void write(){
    freopen("damesah.out", "w", stdout);
    for(i=1; i<=n; ++i) printf("%d ", sol[i]);
    printf("\n%lld\n", cnt);
    fclose(stdout);
}
void bkt(int line){
    if(line==n+1){
        ++cnt;
        if(cnt==1) for(int i=1; i<=n; ++i) sol[i]=lst[i];
        return;
    }
    for(int column=1; column<=n; ++column){
        if(diagL[line-column+n] || diagR[line+column] || col[column]) continue;
        diagL[line-column+n]=diagR[line+column]=col[column]=true;
        lst[line]=column;
        bkt(line+1);
        diagL[line-column+n]=diagR[line+column]=col[column]=false;
    }
}