#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int sol,n,x[50];
bitset <50> f,p,s;
void bt(int k) {
    int i;
    if (k>n){
        sol++;
        if (sol==1){
            for (i=1;i<=n;i++)
                fout<<x[i]<<" ";
        }
        return ;
    }
	for (i=1;i<=n;i++){
		x[k]=i;
		if (!f[i] && !p[n+i-k] && !s[i+k]){
			f[i]=1;
			p[n+i-k]=1;
			s[i+k]=1;
			bt(k+1);
			f[i]=0;
			p[n+i-k]=0;
			s[i+k]=0;
		}
	}
}
int main() {
    fin>>n;
    bt(1);
    fout<<"\n"<<sol;
    return 0;
}