#include <fstream>
#define DIM 14
using namespace std;
ifstream fin("damesah.in");
ofstream fout("damesah.out");
int n,sol,x[DIM];
bool col[DIM],dp[2*DIM],ds[2*DIM];

void afisare() {
    for (int i=1;i<=n;i++)
        fout<<x[i]<<" ";
}

void backtrack(int k) {
    for (int i=1;i<=n;i++)
        if (col[i]==0 && dp[i-k+n]==0 && ds[i+k]==0) {
            x[k]=i;
            if (k==n) {
                sol++;
                if (sol==1)
                    afisare();
                continue;
            }
            col[i]=1;
            dp[i-k+n]=1;
            ds[i+k]=1;
            backtrack(k+1);
            col[i]=0;
            dp[i-k+n]=0;
            ds[i+k]=0;
        }
}

int main() {
    fin>>n;
    backtrack(1);
    fout<<"\n"<<sol;
    return 0;
}