#include<fstream>
#include<cmath>
using namespace std;
int n,i,st[20],k,nr;
ifstream f("damesah.in");
ofstream g("damesah.out");
void init(){
st[k]=0;
}

int am_succesor(){
if(st[k]<n){st[k]++;return 1;}return 0;
}

int e_valid(){
for(i=1;i<k;i++)
if((st[i]==st[k])||(abs(st[k]-st[i])==abs(k-i)))return 0;
return 1;
}

int sol(){return k==n;}

void tipar(){ nr++;
if(nr<=1)for(i=1;i<=n;i++)
g<<st[i]<<" ";

}

void back(){
int as;
k=1;init();
while(k>0){
    do{}while((as=am_succesor())&&!e_valid());
    if(as)
        if(sol())tipar();
    else{k++;init();}
    else k--;}}

int main(){
f>>n;
back();
g<<"\n"<<nr;
f.close();
g.close();
return 0;}