#include <fstream>
#include <string.h>
#define NMax 15
using namespace std;
ifstream f("damesah.in");
ofstream g("damesah.out");
int n, col[NMax], sol[NMax], nrsol, l[NMax], c[NMax], ds[NMax], dp[NMax], ok, viz[NMax];
int ver()
{
    for (int i=1; i<=n; i++) {
        if (l[i] == 0)
            l[i]=1;
        else
            return 0;
        if (c[col[i]] == 0)
            c[col[i]]=1;
        else
            return 0;
        if (dp[i+col[i]-1] == 0)
            dp[i+col[i]-1]=1;
        else
            return 0;
        if (ds[i+n-col[i]] == 0)
            ds[i+n-col[i]]=1;
        else
            return 0;
    }
    return 1;
}
void back(int k)
{
    for (int i=1; i<=n; i++) {
        if (viz[i]==0) {
            viz[i]=1;
            col[k]=i;
            if (k==n) {
                if(ver()) {
                    if (ok==0)
                        for (int i=1; i<=n; i++)
                            sol[i]=col[i];
                    nrsol++;
                    ok=1;
                }
                memset (l, 0, sizeof(l));
                memset (c, 0, sizeof(c));
                memset (dp, 0, sizeof(dp));
                memset (ds, 0, sizeof(ds));
            }
            else
                back(k+1);
            viz[i]=0;
        }
    }
}
int main()
{
    f>>n;
    back(1);
    for (int i=1; i<=n; i++)
        g<<sol[i]<<" ";
    g<<"\n";
    g<<nrsol;
    return 0;
}