#include <bits/stdc++.h>
#define val 100
#define pb push_back

using namespace std;

ifstream f("universal.in");
ofstream g("damesah.out");

int n,sol=0,c[val],l[val],d1[val],d2[val],rez[val],size=1;
bool ok=true;
void place(int i, int j, int value){
	l[i]+=value;
	c[j]+=value;
	d1[n+i-j]+=value;
	d2[i+j]+=value;
}

bool is_free(int i, int j){
	return (l[i]==0 && c[j]==0 && d1[i-j+n]==0 && d2[i+j]==0);
}

void back(int i){
	if (i>n){
		ok=false;
		++sol;
		return ;
	}

	for(int j=1;j<=n;++j){
		if(is_free(i,j)){
			place(i,j,1);
			if(ok)	rez[++size]=j;
			back(i+1);
			place(i,j,-1);
			if(ok)	--size;
		}
	}
}

int main(){

	f>>n;
	back(1);
	for (int i=2;i<=size;++i)
		cout<<rez[i]<<" ";
	cout<<"\n"<<sol<<"\n";

	return 0;
}