#include <iostream>
#include <fstream>
#include <vector>
#define DN 25
using namespace std;

int n,c[DN],d1[DN],d2[DN],nrs;
vector<int> r,sc;

void bk(int lc) {
    if(lc==n+1) {
        if(sc.size()>r.size()) {
            r=sc;
            nrs=1;
        }else if(sc.size()==r.size()) ++nrs;
        return;
    }
    for(int i=1; i<=n; ++i) if(!c[i] && !d1[lc+i] && !d2[lc-i+n]) {
        c[i]=d1[lc+i]=d2[lc-i+n]=1;
        sc.push_back(i);
        bk(lc+1);
        sc.pop_back();
        c[i]=d1[lc+i]=d2[lc-i+n]=0;
    }
}

int main() {
    ifstream f("damesah.in");
    ofstream g("damesah.out");
    f>>n;
    bk(1);
    for(auto i:r) cout<<i<<' ';
    g<<'\n'<<nrs;
}