#include <fstream>
#include <bitset>
using namespace std;
int x[50];
bitset<50> f,p,s;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,sol;
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[n+i-k]&&!s[i+k]&&!f[i]) {
			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;
}