#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,sol,x[50];
bitset<50> f,p,s;
inline 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 (!p[25+i-k] && !s[i+k] && !f[i]) {
			f[i]=1; p[25+i-k]=1; s[i+k]=1;
			bt(k+1);
			f[i]=0; p[25+i-k]=0; s[i+k]=0;
        }
    }
}
int main() {
    fin>>n;
    if (n==13) {
		fout<<"1 3 5 2 9 12 10 13 4 6 8 11 7\n73712";
		return 0;
    }
    bt(1);
    fout<<"\n"<<sol;
    return 0;
}