#include <fstream>
#include <cmath>

using namespace std;

ifstream f("damesah.in");
ofstream g("damesah.out");

bool v[15];
bool d1[60];
bool d2[60];
int sol[15];
int x[15], k = 0;
int n;

bool bkt(int i) {
    for(int j = 1; j <= n; j ++)
    if(!v[j] && !d1[20 + j - i] && !d2[i + j]) {
        x[i] = j;
        if(i == n) {
            if(!k) for(int l = 1; l <= n; l ++) sol[l] = x[l];
            k ++;
            continue;
        }
        v[j] = true;
        d1[20 + j - i] = true;
        d2[i + j] = true;
        bkt(i + 1);
        v[j] = false;
        d1[20 + j - i] = false;
        d2[i + j] = false;
    }
}

int main()
{
    f >> n;
    bkt(1);
    for(int i = 1; i <= n; i ++) g << sol[i] << " ";
    g << "\n" << k << "\n";
    return 0;
}