#include <bits/stdc++.h>
///N=13
using namespace std;
///
int n, i, j, k;
long long cnt;
int lst[20], sol[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){
    for(int column=1; column<=n; ++column){
        bool good=true;
        for(int i=1; i<line; ++i){
            if(abs(i-line)==abs(lst[i]-column) || lst[i]==column) {
                good=false;
                break;
            }
        }
        if(good){
            lst[line]=column;
            if(line==n){
                ++cnt;
                if(cnt==1) for(int i=1; i<=n; ++i) sol[i]=lst[i];
                return;
            }
            bkt(line+1);
        }
    }
}