#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) g<<i<<' ';
g<<'\n'<<nrs;
}