#include <fstream>
#include <bitset>

using namespace std;

ifstream fin  ("damesah.in");
ofstream fout ("damesah.out");

int b, n, x[50];
bitset <50> c, p, s;

void bkt (int k){
    int i;
    if (k > n){
        b++;
        if (b == 1){
            for (i=1; i<=n; i++){
                fout << x[i] << " ";
            }
        }
        return ;
    }
    else{
        for (i=1; i<=n; i++){
            x[k] = i;
            if (c[i] == 0 && p[n+i-k] == 0 && s[i+k] == 0){
                c[i] = 1;
                p[n+i-k] = 1;
                s[i+k] = 1;
                bkt(k+1);
                c[i] = 0;
                p[n+i-k] = 0;
                s[i+k] = 0;
            }
        }
    }
}

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