#include <fstream>
#define nmax 15
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n,v[nmax],sol;
int uz[nmax],dp[nmax*2],ds[nmax*2];


void bkt(int nr)
{
    int i;
    if (nr>n) {
        sol++;
        if (sol==1) {
            for (i=1;i<=n;i++)
                g<<v[i]<<' ';
            g<<'\n';
        }
        return;
    }
    for (i=1;i<=n;i++)
        if (uz[i]==0&&dp[i-nr+nmax]==0&&ds[i+nr]==0) {
            v[nr]=i;
            uz[i]=1;
            dp[v[nr]-nr+nmax]=1;
            ds[nr+v[nr]]=1;
            bkt(nr+1);

            uz[i]=0;
            ds[nr+v[nr]]=0;
            dp[v[nr]-nr+nmax]=0;
            v[nr]=0;
        }


}
int main()
{
    int i,j;
    f>>n;
    bkt(1);
    g<<sol<<'\n';

    return 0;
}