#include <iostream>
#include<stdlib.h>
#include <fstream>
using namespace std;
ifstream f("damesah.in");
ofstream o("damesah.out");

int x[13];
int solutie[13];


void tiparesteSolutie(int n) {
for(int i=1;i<=n;i++){
solutie[i]=x[i];
}
}

bool eValid(int k){
for(int i=1;i<k;i++){
if((x[k]==x[i])||(k-i==abs(x[k]-x[i]))){
return false;
}
}
return true;
}

int backtrack(int n){
int eSolutie, k;
k=1;
x[k]=0;
int nrSolutii=0;
int prima=1;
while(k>0){
eSolutie=0;
while((x[k]<n)&&(!eSolutie)){
x[k]++;
eSolutie=eValid(k);
}
if(!eSolutie){
k--;
} else {
if(k==n){
if (prima){
tiparesteSolutie(n);
prima=0;
}
nrSolutii++;
}
else {
k++;
x[k]=0;
}
}
}
return nrSolutii;
}

int main(){
int n, k, eSolutie;
f>>n;
int nrSolutii=backtrack(n);
for(int i=1;i<=n;i++){
o<<solutie[i]<<" ";
}
o<<'\n';
o<<nrSolutii;
return 0;
}