#include <fstream>

using namespace std;

int n, nr, v[15], f[15], g[2000], t[2000];

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

void back(int niv){
    if(niv == n+1){
        if(nr == 0){
            for(int i = 1;i<=n;i++)
                fout<<v[i]<<" ";
        }
        nr++;
        return;
    }
    for(int i = 1;i<=n;i++){
        int m = i - niv + 20;
        if(f[i] == 0 && g[niv + i] == 0 && t[m] == 0){
            f[i] = 1;
            g[niv + i] = 1;
            t[m] = 1;
            v[niv] = i;
            back(niv+1);
            f[i] = 0;
            g[niv + i] = 0;
            t[m] = 0;
        }
    }
}

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