#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("damesah.in");
ofstream out("damesah.out");

int n,st[14],nrsol,stf[15];

void afis(){
int i,j;
if(nrsol==0)
for(i=1 ;i<=n; i++){
for(j=1 ;j<=n; j++){

if(st[j]==i)
stf[j]=i;
}
}
nrsol++;
}

int valid(int p){
int ok=1,i;
for(i=1;i<p;i++){
if(st[i]==st[p]) ok=0;
if(abs(st[i]-st[p])==p-i) ok=0;
}
return ok;
}


void backt(int k){
int j;
for(j=1;j<=n;j++){
st[k]=j;
if(valid(k)==1)
if(k==n)
afis();
else backt(k+1);
}
}



int main(){
int i,j;
in>>n;

backt(1);

for(i=1;i<=n;i++){
out<<stf[i]<<" ";
}
out<<endl;
out<<nrsol;


return 0;
}